【Day 72 】2022-02-21 - 78. 子集

[azl397985856]

78. 子集

入选理由

暂无

题目地址

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

前置知识

• 位运算
• 回溯

  题目描述

  
  给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

 

示例 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 中的所有元素 互不相同

[yetfan]

思路 递归，每个数考虑要和不要两种情况

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        tmp = []
        n = len(nums)
        def dfs(x):
            if x == n:
                res.append(tmp[:])
                return 
            else:
                tmp.append(nums[x])
                dfs(x+1)
                tmp.pop()
                dfs(x+1)
        dfs(0)
        return res

复杂度 时间 O(2^n) 空间 O(n)

[ZJP1483469269]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        vis = [0] * n
        def backtarck(i , x):
            if i == n:
                ans.append(x)
                return
            for j in range(i,n):
                if not vis[j]:
                    vis[j] = 1
                    backtarck(i + 1 , x )
                    backtarck(i + 1 , x + [nums[j]])
                    vis[j] = 0                
        backtarck(0 , [])            
        return ans

[LAGRANGIST]

day72-78. 子集

题目描述

78. 子集

难度 中等

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

示例 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 中的所有元素 互不相同

思路

• 最开始想到dfs暴力回溯
• 然后想到可以用二进制表示状态进行一个状态压缩
• 可以将每个元素选或不选的状态映射到一个长度为nums.size()`的二进制数的每一位是 0 还是 1
• 接着通过从二进制数 0 一直枚举到允许的最大数，然后通过位运算操作找出哪些位是 1，然后将满足i[j] == 1 对应的 nums[j] 添加到子集中
• 将所有该数字对应的数字加入到子集后，便可以将该子集添加到 vector<int> ans 中

代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        int sum = 1 << nums.size();
        vector<int> temp;
        for(int i = 0;i < sum;i++)
        {
            temp.clear();
            for(int j = 0; (i >> j) > 0; j++) // 看这个二进制数 i 哪一位是 1
            {
                if( ((i >> j) & 1) == 1 )
                {
                    temp.push_back(nums[j]) ; // i 的第 j 位是 1
                }
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

复杂度

• 时间： $O(n^2)$

[ZacheryCao]

Idea

Backtracking

Code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> cur;
        backtracking(nums, ans, 0, cur);
        return ans;
    }

    void backtracking(vector<int>& nums,vector<vector<int>>& ans, int start, vector<int>& cur){
        ans.push_back(cur);
        if(start >= nums.size())
            return;
        for(int i = start; i<nums.size(); ++i){
            cur.push_back(nums[i]);
            backtracking(nums, ans, i+1, cur);
            cur.pop_back();
        }
    }
};

Complexity:

Time: O(N * 2^N) Space: O(N)

[moirobinzhang]

Code：

public IList<IList<int>> Subsets(int[] nums) {
    IList<IList<int>> res = new List<IList<int>>();
    IList<int> numSet = new List<int>();

    if (nums == null || nums.Length == 0)
        return res;

    Array.Sort(nums);

    SubSetsHelper(nums, res, numSet, 0);

    return res;        
}

public void SubSetsHelper(int[]  nums, IList<IList<int>> res, IList<int> numSet, int index)
{
    res.Add(new List<int>(numSet));

    for (int i = index; i < nums.Length; i++)
    {
        numSet.Add(nums[i]);
        SubSetsHelper(nums, res, numSet, i + 1);
        numSet.RemoveAt(numSet.Count - 1);
    }

}

[rzhao010]

xclass Solution {
    List<Integer> t = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int cur) {
        if (cur == nums.length) {
            res.add(new ArrayList<Integer>(t));
            return;
        }
        // include cur
        t.add(nums[cur]);
        dfs(nums, cur + 1);
        t.remove(t.size() - 1);
        dfs(nums, cur + 1);
    }
}

Complexity Time: O(n * 2 ^ n) Space: O(n)

[feifan-bai]

思路 1.回溯

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

复杂度分析

• 时间复杂度：O(N*2**N)
• 空间复杂度：O(N)

[zjsuper]

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

        for i in range(len(nums)):
            res += [[nums[i]]+j for j in res]

        return res

[zhangzz2015]

思路

• 可使用回溯，也可使用bit位压缩方法，把每一位num看做一个bit位置，每个位置上有两个状态，1为选择，2为不选择，0可表示不选择，1则表示选择，总共的状态为2^n，时间复杂度为2^n * n ，空间复杂度为O(n)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {

        // bit 
        vector<vector<int>> ret; 
        for(int mask =0; mask< (1<<(nums.size())); mask++ )
        {
            vector<int> onePath; 
            for(int i=0; i< nums.size(); i++)
            {
                if(mask & (1<<(i)))
                {
                    onePath.push_back(nums[i]); 
                }                
            }
            ret.push_back(onePath); 
        }
        return ret; 

    }
};

[wdwxw]

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

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;
}

}

[Bochengwan]

思路

利用位运算，每个num可以是on或者off，combine每个不同位的状态n。

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        for i in range(1<<n):
            curr=[]
            for j in range(n):
                if (i>>j)&1:
                    curr.append(nums[j])
            ans.append(curr)
        return ans

复杂度分析

• 时间复杂度：O(N*2^N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[Alexno1no2]

# 1.开始定义res = [[]]
# 2.然后对nums遍历（以nums = [1,2,3]为例）
# （1）第一次，i=1：对ans遍历，① ans=[[]],ans加1, ans = [[],[1]]
# （2）第二次, i=2：对ans遍历，ans=[[],([],[1])]
# j=[] , ans =[[],([],[1]),([],[2])]
# j=([],[1]), ans =[[],([],[1]),([],[2]),([],[1],[2])]
# ……

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

[james20141606]

Day 72: 78. Subsets (recursion, backtrack, bit)

• Problem Link

  • 78. Subsets

• Ideas

  • use recursion or backtracking. For recursion, we could use bit operation to enumerate all the combinations.

• Complexity: hash table and bucket

  • Time: O(N*2**N)
  • Space: O(N)

• Code

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

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]
        return res

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res  

class Solution:
    def subsets(self, nums):
        res, end = [], 1 << len(nums) #2**len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                #print (i, 1 << i, sign, (1 << i) & sign)
                if ((1 << i) & sign) != 0: #means that if we select the ith position! 
                    subset.append(nums[i])
            res.append(subset)
        return res

• other resources:
  • similar questions: https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/

[QinhaoChang]

思路： dfs+ backtracking

代码： class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] temp = []

    self.dfs(nums, res, temp, 0)
    return res

def dfs(self, nums, res, temp, index):
    res.append(temp[:])

    for i in range(index, len(nums)):
        temp.append(nums[i])
        self.dfs(nums, res, temp, i + 1)
        temp.pop()

[CoreJa]

思路

• 位运算：集合中某元素存在或不存在有两种状态，这些状态的组合构成了集合的所有子集。将某元素的存在和不存在表示为1和0，则从0循环到2^n-1，保留位数为1在数组中对应的元素，即可得到所有子集。复杂度$O(n*2^n)$
• 一行位运算：一行代码简化流程。复杂度$O(n*2^n)$
• 数学：另一个得到子集的方式是递增，对于n个元素集合，如果已知前i个元素集合的子集ans，则前i+1个元素的子集只用考虑前面的子集带上第i+1个元素或者不带这两种情况。复杂度$O(n*2^n)$

代码

class Solution:
    # 位运算：集合中某元素存在或不存在有两种状态，这些状态的组合构成了集合的所有子集。将某元素的存在和不存在表示为1和0，
    # 则从0循环到`2^n-1`，保留位数为1在数组中对应的元素，即可得到所有子集。复杂度$O(n*2^n)$
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for i in range(1 << len(nums)):
            idx = 0
            tmp = []
            while i:
                if i & 1:
                    tmp.append(nums[idx])
                idx += 1
                i >>= 1
            ans.append(tmp)
        return ans

    # 一行位运算：一行代码简化流程。复杂度$O(n*2^n)$
    def subsets2(self, nums: List[int]) -> List[List[int]]:
        return [[nums[j] for j in range(len(nums)) if 1 << j & i] for i in range(1 << len(nums))]

    # 数学：另一个得到子集的方式是递增，对于n个元素集合，如果已知前`i`个元素集合的子集`ans`，则前`i+1`个元素的子集只用考虑
    # 前面的子集带上第`i+1`个元素或者不带这两种情况。复杂度$O(n*2^n)$
    def subsets3(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        for num in nums:
            ans += [arr + [num] for arr in ans]
        return ans

[JudyZhou95]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

    """
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtrack(res, nums, [], -1)

        return res
    def backtrack(self, res, nums, temp, ind):

        res.append(temp)
        for i in range(ind+1, len(nums)):
            self.backtrack(res, nums, temp+[nums[i]], i)
    """        

    """
    def subsets(self, nums: List[int]) -> List[List[int]]:

        res = [[]]        
        for n in nums:            
            res += [s+[n] for s in res]
        return res
    """

[yan0327]

func subsets(nums []int) [][]int {
    out := [][]int{}
    var dfs func(temp []int,index int)
    dfs = func(temp []int,index int){
        if index == len(nums){
            out = append(out,append([]int{},temp...))
            return
        }
        temp = append(temp,nums[index])
        dfs(temp,index+1)
        temp = temp[:len(temp)-1]
        dfs(temp,index+1)
    }
    dfs([]int{},0)
    return out
}

[Serena9]

代码

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

[baddate]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res  

[Toms-BigData]

func subsets(nums []int) (ans [][]int) {
    n:=len(nums)
    for mask := 0; mask < 1<<n; mask++ {
        set := []int{}
        for i, v := range nums {
            if mask>>i&1 > 0{
                set = append(set, v)
            }
        }
        ans = append(ans, set)
    }
    return ans
}

[Tesla-1i]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        tmp = []
        n = len(nums)
        def dfs(x):
            if x == n:
                res.append(tmp[:])
                return 
            else:
                tmp.append(nums[x])
                dfs(x+1)
                tmp.pop()
                dfs(x+1)
        dfs(0)
        return res

[1149004121]

78. 子集

思路

位运算。假设有n个数，用一个二进制数表示某个子集，则用1表示有这数，0表示没这数。

代码

var subsets = function(nums) {
    const n = nums.length;
    let res = [];
    for(let mask = 0; mask < (1 << n); mask++){
        let temp = [];
        for(let i = 0; i < n; i++){
            if(mask & (1 << i)){
                temp.push(nums[i]);
            }
        };
        res.push(temp);
    };
    return res;
};

复杂度分析

• 时间复杂度：O(N * 2 ^ {N} )。
• 空间复杂度：O(N)。

[xuhzyy]

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        res = []

        def backtrack(start, path):
            res.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i+1, path)
                path.pop()

        backtrack(0, [])
        return res

[KennethAlgol]

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

复杂度分析

时间复杂度 O(2n)

[xinhaoyi]

class Solution { public List<List> subsets(int[] nums) { List<List> res = new ArrayList<>(); List path = new ArrayList<>(); subsets(nums, 0, path, res); return res; }

private void subsets(int[] nums, int start, List<Integer> path, List<List<Integer>> res){
    //回溯
    res.add(new ArrayList<>(path));
    for(int i = start; i < nums.length; i++){
        //把结点先加进去
        path.add(nums[i]);
        //debug：一定注意这里是i+1，不是start+1
        subsets(nums, i+1, path, res);
        //到最深层了之后，要回溯，把先前最后加进去的点吐出来
        path.remove(path.size() - 1);
    }
}

}

[charlestang]

思路

回溯法。

对于每个元素来说，可以选择加入集合或者不加入集合。

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        def dfs(i: int, s: List[int]):
            if i == n:
                ans.append(s)
            else:
                dfs(i + 1, s)
                dfs(i + 1, s + [nums[i]])
        dfs(0, [])
        return ans

时间复杂度 O(2^n)

空间复杂度 O(n^2)

[haixiaolu]

思路

回溯

代码 / python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # Backtracking

        res = []

        subset = []
        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return

            # decision to include nums[i]
            subset.append(nums[i])
            dfs(i + 1)

            # decision not to include nums[i]
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res 

• Time: O(2^n)
• Space: O(n)

[zol013]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        all_possible = 1 << len(nums)

        for state in range(all_possible):
            subset = []
            for i in range(len(nums)):
                if state & (1 << i) != 0:
                    subset.append(nums[i])
            ans.append(subset)

        return ans

[anyingbinglong]

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ans = [] all_possible = 1 << len(nums)

    for state in range(all_possible):
        subset = []
        for i in range(len(nums)):
            if state & (1 << i) != 0:
                subset.append(nums[i])
        ans.append(subset)

    return ans

[ACcentuaLtor]

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: n = len(nums) ans = [] def dfs(i: int, s: List[int]): if i == n: ans.append(s) else: dfs(i + 1, s) dfs(i + 1, s + [nums[i]]) dfs(0, []) return ans

[LannyX]

思路

backtrack

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int n;
    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        for(int k = 0; k <= n; k++){
            backtrack(0, k, new ArrayList<Integer>(), nums);
        }
        return res;
    }
    void backtrack(int start, int k, ArrayList<Integer> cur, int[] nums){
        if(k == 0){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        for(int i = start; i < n; i++){
            cur.add(nums[i]);
            backtrack(i + 1, k - 1, cur, nums);
            cur.remove(cur.size() - 1);
        }
    }
}

[zhiyuanpeng]

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0:
                    subset.append(nums[i])
            res.append(subset)
        return res

[jiaqiliu37]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        all_possible = 1 << len(nums)

        for state in range(all_possible):
            subset = []
            for i in range(len(nums)):
                if state & (1 << i)!= 0:
                    subset.append(nums[i])
            ans.append(subset)

        return ans

Time complexity O(n*2^n)

[tongxw]

思路

位运算，枚举

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        int size = 1 << n;
        for (int i=0; i<size; i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j=0; j<n; j++) {
                int mask = i & (1 << j);
                if (mask != 0) {
                    subset.add(nums[j]);
                }
            }
            ans.add(subset);
        }

        return ans;
    }
}

TC: O(n 2^N) SC: O(n 2^N)

[callmeerika]

思路

位运算

代码

var subsets = function(nums) {
    const res = [];
    const n = nums.length;
    for (let i = 0; i < 1 << n; i++) {
      let tmp = [];
      for (let j = 0; j < n; j++) {
        if (i & (1 << j)) {
          tmp.push(nums[j]);
        }
      }
      res.push(tmp);
    }
    return res;
};

复杂度

事件复杂度：O(n*2^n)
空间复杂度：O(n)

[falconruo]

思路: backtracking

复杂度分析:

• 时间复杂度: O(N*2^N)，N为数组nums的长度
• 空间复杂度: O(N)

代码(C++):

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> subset;

        backTracking(nums, 0, subset, res);

        return res;
    }
private:
    void backTracking(vector<int>& nums, int pos, vector<int>& subset, vector<vector<int>>& res) {
        res.push_back(subset);

        if (pos >= nums.size()) return;

        for (int i = pos; i < nums.size(); i++) {
            subset.push_back(nums[i]);
            backTracking(nums, i + 1, subset, res);
            subset.pop_back();
        }
    }
};

[Richard-LYF]

class Solution: def init(self): self.path = [] self.paths = []

def subsets(self, nums: List[int]) -> List[List[int]]:

    self.backtracking(nums,0)

    return self.paths

def backtracking(self,nums,start_indedx):

    self.paths.append(self.path[:])
    if start_indedx == len(nums):
        return 

    for i in range(start_indedx,len(nums)):
        self.path.append(nums[i])
        self.backtracking(nums,i + 1)
        self.path.pop()

[hdyhdy]

var res [][]int
func subsets(nums []int) [][]int {
    res = make([][]int, 0)
    sort.Ints(nums)
    Dfs([]int{}, nums, 0)
    return res
}
func Dfs(temp, nums []int, start int){
    tmp := make([]int, len(temp))
    copy(tmp, temp)
    res = append(res, tmp)
    for i := start; i < len(nums); i++{
        //if i>start&&nums[i]==nums[i-1]{
        //  continue
        //}
        temp = append(temp, nums[i])
        Dfs(temp, nums, i+1)
        temp = temp[:len(temp)-1]
    }
}

[CodingProgrammer]

思路

回溯

代码

class Solution {
    List<List<Integer>> ans;
    LinkedList<Integer> path;
    int n;
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length > 10) {
            throw new IllegalArgumentException();
        }
        ans = new ArrayList<>();
        path = new LinkedList<>();
        n = nums.length;
        boolean[] usedPath = new boolean[n];
        backtracking(nums, usedPath, 0);
        return ans;
    }

    private void backtracking(int[] nums, boolean[] usedPath, int idxStart) {
        ans.add(new ArrayList(path));

        // 树枝去重
        for (int i = idxStart; i < n; i++) {
            if (usedPath[i] == true) continue;
            path.addLast(nums[i]);
            usedPath[i] = true;
            backtracking(nums, usedPath, i);
            usedPath[i] = false;
            path.removeLast();
        }
    }
}

复杂度

• 时间复杂度：O(N*2^N)
• 空间复杂度：O(N)

[biscuit279]

思路：

循环

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        q=[[]]
        n=len(nums)
        for i in range(n):
            for j in range(len(q)):
                q.append(q[j]+[nums[i]])
        return q

时间复杂度：O(n**2） 空间复杂度：O(n)

[Aobasyp]

思路 位运算

class Solution { public: vector<vector> subsets(vector& nums) { int n = nums.size(); vector t; vector<vector> res; 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]); } } res.push_back(t); } return res; } };

时间复杂度：O(N*2^N) 空间复杂度：O(N)

[Myleswork]

思路

基础的回溯

代码

class Solution {
public:
    vector<vector<int>> res= {{}};
    vector<int> cur;
    void backtrack(vector<int>& nums,int start){
        int len = nums.size();
        for(int i = start;i<len;i++){
            cur.push_back(nums[i]);
            res.push_back(cur);
            backtrack(nums,i+1);
            cur.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums,0);
        return res;
    }
};

复杂度分析

时间复杂度：O(len)

空间复杂度：O(len)

[alongchong]

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;
    }
}

[shamworld]

var subsets = function(nums) {
    const ans = [];
    const n = nums.length;
    for (let mask = 0; mask < (1 << n); ++mask) {
        const t = [];
        for (let i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t.push(nums[i]);
            }
        }
        ans.push(t);
    }
    return ans;
};

[hx-code]

var subsets = function(nums) { const ans = []; const n = nums.length; for (let mask = 0; mask < (1 << n); ++mask) { const t = []; for (let i = 0; i < n; ++i) { if (mask & (1 << i)) { t.push(nums[i]); } } ans.push(t); } return ans; };

[HWFrankFung]

Codes

var subsets = function(nums) {
    var res=new Array();//result
    var path=new Array();//current path
    var index=new Array();//current path indexes
    var curindex=0;//current index
    const backtracking=function(l,path,curindex){
        if(path.length==l){
            res.push(path.slice());
            return;
        }
        for(let i=curindex;i<nums.length;i++){
            path.push(nums[curindex]);
            index.push(curindex);
            backtracking(l,path,curindex+1);
            path.pop();
            curindex=index.pop()+1;
        }
    }
    for(let j=0;j<=nums.length;j++){
        backtracking(j,path,curindex);
    }
    return res;
};

[guangsizhongbin]

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 }

[15691894985]

class Solution: def subsets(self, nums): res, end = [], 1 << len(nums) for sign in range(end): subset = [] for i in range(len(nums)): if ((1 << i) & sign) != 0: #用第 i 位是 1 比特与当前 sign 相与，若结果不为 0 就代表第 i 位比是 1 subset.append(nums[i]) res.append(subset) return res 时间复杂度:O(n*2^n)一共 2^n 个状态，每种状态需要 O(n)的时间来构造子集

空间复杂度：O(n)

[15691894985]

class Solution:
    def subsets(self, nums):
        res, end = [], 1 << len(nums)
        for sign in range(end):
            subset = []
            for i in range(len(nums)):
                if ((1 << i) & sign) != 0: #用第 i 位是 1 比特与当前 sign 相与，若结果不为 0 就代表第 i 位比是 1
                    subset.append(nums[i])
            res.append(subset)
        return res

时间复杂度:O(n*2^n)一共 2^n 个状态，每种状态需要 O(n)的时间来构造子集

空间复杂度：O(n)

[dahaiyidi]

Problem

[78. 子集](https://leetcode-cn.com/problems/subsets/)

++

难度中等1485

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

---

Note

• 最基本的回溯
• 将回溯与树的DFS遍历相结合。

---

Complexity

• 时间O：n*2^n
• 空间O：n

---

Python

C++

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, res, path, 0);
        return res;
    }
    void backtrack(vector<int>& nums, vector<vector<int>> & res, vector<int> & path, int start){
        // if(start >= nums.size()){
        //     return;
        // }

        res.push_back(path);

        // 有点像树的遍历
        for(int i = start; i < nums.size(); i++){
            path.push_back(nums[i]);

            // 当前级选择当前元素，进入下一级
            backtrack(nums, res, path, i + 1);

            // 同一级，切换到下一个元素
            path.pop_back();
        }

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode