search

leetcode-pp / 91alg-9-daily-check

5 stars 0 forks source link

【Day 72 】2023-01-11 - 78. 子集 #79

Open azl397985856 opened 1 year ago

azl397985856 commented 1 year ago

78. 子集

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/subsets/

前置知识

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2：

输入：nums = [0] 输出：[[],[0]]  

提示：

1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素 互不相同

whoam-challenge commented 1 year ago

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums)+1): for tmp in itertools.combinations(nums, i): res.append(tmp) return res

snmyj commented 1 year ago 
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> result;
        vector<int> t;
        for(int i=0;i<(1 << n);i++){
           t.clear();
           for(int j=0;j<n;j++){
               if(i&(1<<j)){
                   t.push_back(nums[j]);
               }
           }
           result.push_back(t);
        }
        return result;
    }
};
arinzz commented 1 year ago

class Solution { public List<List> subsets(int[] nums) { List<List> res = new ArrayList<>(); res.add(new ArrayList<>()); for (int i = 0; i < nums.length; i++) { int all = res.size(); for (int j = 0; j < all; j++) { List tmp = new ArrayList<>(res.get(j)); tmp.add(nums[i]); res.add(tmp); } } return res; } }

Abby-xu commented 1 year ago

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ret = [] self.dfs(nums, [], ret) return ret

def dfs(self, nums, path, ret):
    ret.append(path)
    for i in range(len(nums)):
        self.dfs(nums[i+1:], path+[nums[i]], ret)
JancerWu commented 1 year ago 

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0, new ArrayList<>());
        return ans;
    }
    public void dfs(int[] nums, int i, List<Integer> tmp) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        dfs(nums, i + 1, tmp);
        tmp.add(nums[i]);
        dfs(nums, i + 1, tmp);
        tmp.remove(tmp.size()-1);

    }

}
buer1121 commented 1 year ago

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: path=[] paths=[]

    def backtrack(nums,start_index):
        paths.append(path[:])
        if start_index==len(nums):
            return
        for i in range(start_index,len(nums)):
            path.append(nums[i])
            backtrack(nums,i+1)
            path.pop()

    backtrack(nums,0)
    return paths
ringo1597 commented 1 year ago

代码

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}
zjsuper commented 1 year ago

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ans = [] length = len(nums) def dfs(idx,path): if idx == length: ans.append(path[:]) return else: path.append(nums[idx]) dfs(idx+1,path) path.pop() dfs(idx+1,path)

    dfs(0,[])  
    return ans
Elsa-zhang commented 1 year ago 
# 78. 子集
''' 枚举 mask∈[0,2**n-1] 
    时间复杂度: O(nx2**n)
    空间复杂度: O(n)
'''
class Solution:
    def subsets(self, nums: list[int]):
        n = len(nums)
        num_mask = 2**n
        ans = []
        for i in range(num_mask):
            # mask = bin(i)
            sub = []
            for j in range(n):
                num = nums[j]
                if i & (1<<j):
                    sub.append(num)
            ans.append(sub)

        return ans

nums = [1,2,3]
s = Solution()
ans = s.subsets(nums)
print(ans)
RestlessBreeze commented 1 year ago

code

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
};
mayloveless commented 1 year ago

思路

每个数字都有两种状态，所以有 2^n 个解，把每个解都转换成二进制。找到为1的位，找到对应的num组成一个组合。

代码

var subsets = function(nums) {
    const generateOne = (s, nums) => {
        // s 代表一种可能
        // 要找出为1的那几个数
        const arr = [];
        let idx = nums.length-1;
        // 求出每一位
        while(s) {
            if (s & 1) {// 最后一位为1
                arr.unshift(nums[idx])// 加入
            }
            idx--;
            s >>= 1;// 挪动一位
        }
        return arr;
    }

    let res = [];
    let n = nums.length;
    for (let i = 0; i < 2 ** n; i++) {
        res.push(generateOne(i, nums));
    }
    return res;
};

复杂度

时间：O(N∗2^n) 空间：O(N)

A-pricity commented 1 year ago 
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let result = []
    let path = []
    function backtracking(startIndex) {
        result.push(path.slice())
        for(let i = startIndex; i < nums.length; i++) {
            path.push(nums[i])
            backtracking(i + 1)
            path.pop()
        }
    }
    backtracking(0)
    return result
};
AstrKing commented 1 year ago

代码

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}
klspta commented 1 year ago 
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        process(res, path, nums, 0);
        return res;
    }

    private void process(List<List<Integer>> res, List<Integer> path, int[] nums, int index){
        if(nums.length == index){
            res.add(new ArrayList<>(path));
            return;
        }

        path.add(nums[index]);
        process(res, path, nums, index + 1);
        path.remove(path.size() - 1);
        process(res, path, nums, index + 1);
    }
}
paopaohua commented 1 year ago 
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}
bookyue commented 1 year ago

平时回溯写得多，状态压缩写的少了

code

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> sub = new ArrayList<>();

            for (int j = 0; j < nums.length; j++) {
                if (((1 << j) & i) != 0)
                    sub.add(nums[j]);
            }

            res.add(sub);
        }

        return res;
    }
GG925407590 commented 1 year ago 
func subsets(nums []int)( ans [][]int) {
    set := []int{}
    var dfs func(int)
    dfs = func(cur int,) {
        if cur == len(nums) {
            ans = append(ans, append([]int(nil), set...))
            return
        }
        set = append(set, nums[cur])
        dfs(cur + 1)
        set = set[:len(set) - 1]
        dfs(cur + 1)
    }
    dfs(0)
    return ans;
}
Jetery commented 1 year ago

代码 (cpp)

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        int n  = nums.size();
        vector<int> t;
        for (int i = 0; i < (1 << n); i++) {
            t.clear();
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) t.push_back(nums[j]);
            }
            ans.push_back(t);
        }
        return ans;
    }
};
BruceZhang-utf-8 commented 1 year ago

代码

Java Code:


class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), ans, 0);
        return ans;
    }
    public void backtrack(int[] nums, List<Integer> cur, List<List<Integer>> ans, int k) {
        ans.add(new ArrayList<>(cur));
        for(int i = k; i < nums.length; ++i) {
            cur.add(nums[i]);
            backtrack(nums, cur, ans, i + 1);
            cur.remove(cur.size() - 1);
        }
    }
}
Alexno1no2 commented 1 year ago 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans=[[]]
        for i in nums:
            for j in range(len(ans)):
                ans.append(ans[j]+[i])
        return ans
FlipN9 commented 1 year ago 
/**
    TC: O(N*2^N)    SC: O(N)
*/
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        if (nums == null || nums.length == 0) return result;

        int s = 0;

        for (int n : nums){
            s = result.size();
            for (int i = 0; i < s; i++){
                // 对于之前所有决定,都把当前的新 num 添进去
                List<Integer> set = new ArrayList<>(result.get(i));
                set.add(n);
                result.add(set);
                // System.out.println(set.toString());
            }
        }
        return result;
    }
}
tiandao043 commented 1 year ago

思路

本来觉得是dfs，看了题解发现位运算。

代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int s=nums.size();
        int n=1<<s;
        vector<vector<int>> ans;
        for(int i=0;i<n;i++){
            vector<int> v;
            for(int j=0;j<s;j++){
                if(i&(1<<j))v.push_back(nums[j]);
            }
            ans.push_back(v);
        }
        return ans;
    }
};

O(N∗2 ^N) O(N)

Ryanbaiyansong commented 1 year ago 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        # 不能包含重复的子集
        res = []
        # def backtrack(pos:int, cur: List[int]):
        #     res.append(cur[:])
        #     for i in range(pos, n):
        #         # 选择当前的数字
        #         cur.append(nums[i])
        #         backtrack(i+1, cur)
        #         cur.pop()
        #     return cur

        # backtrack(0, [])
        # return res

        # 选 / 不选的模型
        def backtrack(i: int, cur: List[int]):
            if i >= n:
                res.append(cur[:])
                return 
            cur.append(nums[i])
            backtrack(i+1, cur)
            cur.pop()
            backtrack(i+1, cur)

        backtrack(0, [])
        return res