【Day 72 】2021-11-20 - 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 中的所有元素 互不相同

[yanglr]

思路:

题意: 数组中的元素互不相同.

方法: 位运算

在二进制状态下做状态的轮流变换(1表示选中, 0表示不选中).

代码

实现语言: C++

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        const int n = nums.size();
        vector<vector<int>> res;
        for (int s = 0; s < (1 << n); s++)
        { /* s表示一个状态state, 共有2^n (1 << n)个状态 */
            vector<int> curSet;
            for (int i = 0; i < n; i++)
                if ((s & (1 << i)) > 0) /* 从末位开始, 循环判断当前位是不是1. 注意位运算的优先级不比+、>、<、=高, 可以加括号后判断>0, 也可以简写为 if (s & (1 << i)) */
                    curSet.push_back(nums[i]);
            res.push_back(curSet);
        }
        return res;
    }
};

复杂度分析

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

[yj9676]

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

[kidexp]

thoughts

让k从0到2^n-1次方进行遍历，这样k的某一个bit为1，那么对应的nums中的数就应该放进去, 这样就能遍历所有的subset

code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        iterative
        """
        end_num = 2 ** len(nums)
        results = []
        for k in range(end_num):
            single_solution = []
            for i in range(len(nums)):
                if (k >> i) & 1 == 1:
                    single_solution.append(nums[i])
            results.append(single_solution)
        return results

complexity

Time O(2^n*n)

Space O(2^n*n))

[cicihou]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        '''
        注意 path 添加的必须是深拷贝，以免后面答案添加之后影响到 res 中的 path
        '''
        res = []
        path = []

        def backtrack(nums, path, start):
            # 注意：其实 nums 这个参数不带也行，从头到尾我们也没修改过 nums
            res.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(nums, path, i+1)
                path.pop()

        backtrack(nums, path, 0)
        return res

        '''
        method 2
        '''
        res = [[]]
        for num in nums:
            res += [cur + [num] for cur in res]
        return res

        '''
        method 3 bit manipulation

        每个元素有两种状态，拿或者不拿，那么如果一共有NN个数，那就一共有 2^N 种可能，也就是有这么多个子集（子集包括全集和空集）。
        既然每一个数只有两种状态，那么我们不妨用一个 bit 来表示。这样题中的[1,2,3]，我们可以看成一个三个比特的组合：
            比如 0 0 0 就代表空集，1 1 1 就代表全集， 1 0 0 就代表[1] (可正可反)。
            这样我们就可以进行位操作，0 - 2^n - 1的数的二进制数位为 1 的位置，就把对应的元素填入集合中。
        PS: ((1 << i )& sign) != 0 的意思是用第 i 位是 1 比特与当前 sign 相与，若结果不为 0 就代表 第 i 位 比是 1

        time: O(N * 2^N)
        space: O(N)
        '''

        # 1 << len(nums) means 2 ** len(nums)
        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

[pophy]

思路1

• backtracking
• 因为没有重复值，不考虑去重 （subsetII)
• 在做选择的时候根据当前的index只能往后选，从而避免重复

Java Code

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

时间&空间

• 时间 O(2^n) 组合数
• 空间 O(n)

思路2

• bitmask

Java Code

    public List<List<Integer>> subsets(int[] nums) {
        int n  = nums.length;        
        List<List<Integer>> res = new ArrayList();
        for (int state = 0; state < (1 << n); state++) {
            List<Integer> path = new ArrayList();
            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) != 0) {
                    path.add(nums[i]);
                }
            }
            res.add(path);
        }            
        return res;
    }

时间&空间

• 时间 O(2^n)
• 空间 O(2^n)

[zhangzz2015]

• 子集和组合问题，可利用回溯方法，建立树，每一个子集为一个遍历树的一个节点。 时间复杂度为O(2^n) ，空间复杂度为O(n*n)

关键点

代码

• 语言支持：C++

C++ Code:

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

        vector<int> onePath; 
        vector<vector<int>> ret; 

        backTrac(nums, 0, onePath, ret); 

        return ret; 

    }

    void backTrac(vector<int>& nums, int start, vector<int>& onePath, vector<vector<int>>& ret)
    {
       // if(start>= nums.size())
       //     return; 

        ret.push_back(onePath); 

        for(int i= start; i< nums.size(); i++)
        {
            onePath.push_back(nums[i]); 

            backTrac(nums, i+1, onePath, ret); 

            onePath.pop_back(); 

        }

    }
};

[zhy3213]

思路

bitmask上瘾

代码

能写一行绝不写两行

    def subsets(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))]

[biancaone]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if nums is None:
            return []
        nums.sort()
        result = []
        self.dfs(nums, result, 0, [])
        return result

    def dfs(self, nums, result, index, path):
        result.append(list(path))

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

[banjingking]

思路

Backtracking

代码

public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> each = new ArrayList<>();
helper(res, each, 1, n, k);
return res;
}
public void helper(List<List<Integer>> res, List<Integer> each, int pos, int n, int k) {
    if (each.size() == k) {
        res.add(each);
        return;
    }
    for (int i = pos; i <= n; i++) {
        each.add(i);
        helper(res, new ArrayList<>(each), i + 1, n, k);
        each.remove(each.size() - 1);
    }
    return;
}

Time complexity

空间复杂度: O(N)

时间复杂度: O(N×2^N)

[yachtcoder]

• Date: 2021-11-19

• Key Insights

  • DFS
  • Backtracking

• Complexity: O(2^n); O(2^n)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        N = len(nums)
        def dfs(idx, path):
            if idx == N:
                nonlocal result
                result.append(path)
                return
            dfs(idx+1, path+[nums[idx]])
            dfs(idx+1, path)
        def bt(idx, path):
            nonlocal result
            result.append(list(path))
            for i in range(idx, N):
                path.append(nums[i])
                bt(i+1, path)
                path.pop()
        result = []
        bt(0, [])
        return result

[JiangyanLiNEU]

Idea

• DFS, Backtracking
• Runtime = O(2^n) Space = 2^n

  JavaScript

  const subsets = (nums) => {
  const n = nums.length;
  const ans = [];
  if (n < 1) return [[]];
  const dfs = (i, curr) => {
      ans.push([...curr]);
      for (let idx=i;idx<n;idx++) {
          curr.push(nums[idx]);
          dfs(idx+1, curr);
          curr.pop();}};
  dfs(0, []);
  return ans;
  };

  Python

  class Solution(object):
  def subsets(self, nums):
      result = []
      if len(nums)==0:
          return result
      def dfs(index, cur):
          result.append(deepcopy(cur))
          for i in range(index, len(nums)):
              cur.append(nums[i])
              dfs(i+1, cur)
              cur.remove(nums[i])
      dfs(0, [])
      return result

  Backtracking

class Solution(object): def subsets(self, nums): if len(nums) == 0: return [] result = [] seen = set([]) def backtracking(cur, index): if index == len(nums): if tuple(cur) not in seen: result.append(cur) else: copy = deepcopy(cur) if tuple(copy) not in seen: result.append(copy) seen.add(tuple(copy)) backtracking(cur+[nums[index]], index+1) backtracking(cur, index+1) backtracking([nums[0]], 1) backtracking([], 1) return result```

[itsjacob]

Intuition

• [tags] backtrack, bit encoding for quick vector container serialization, hashtable
• very first thought is to backtrack to get all the possibilities of subsets, however, we don't want to add the already-added sub vectors into the result, so we need a hashtable to look up if a subvector has been seen before or not. Unfortunately, containers like std::vector can't be hashed unless we define its serialization by ourselves. Since the problem can only contain at most 11 numbers from [-10, 10], and each number is unique, we can serialize the std::vector using 16-bits (2-bytes) int, each index in the array corresponds to one bit in the short int. This only takes O(N) to serialize, as opposed to the sort-then-tokenize approach which is O(NlogN)

Implementation

class Solution
{
public:
  vector<vector<int>> subsets(vector<int> &nums)
  {
    // nums.length <= 10
    // use a 2-bytes short as a hashtable to mark if a subset has been seen before or not

    // a table of encoded vector of indices from the nums
    std::unordered_set<short> table;
    // backtrack helper variable to mark if num has been visted or not
    std::vector<bool> visited(nums.size(), false);
    std::vector<int> subvec;
    std::vector<std::vector<int>> res;

    backtrack(nums.size(), subvec, visited, table, res);

    // convert the indices into nums
    for (auto &subset : res) {
      for (auto &item : subset) {
        item = nums[item];
      }
    }
    return res;
  }

private:
  void backtrack(int n, std::vector<int> &subvec, std::vector<bool> &visited, std::unordered_set<short> &table,
                 std::vector<std::vector<int>> &res)
  {
    // serialize the subvec into a 2-bytes short
    short subvecCode = serialize(subvec);
    if (!table.count(subvecCode)) {
      table.emplace(subvecCode);
      res.emplace_back(subvec);
    }
    for (int ii = 0; ii < n; ii++) {
      if (visited[ii]) continue;
      visited[ii] = true;
      subvec.push_back(ii);
      backtrack(n, subvec, visited, table, res);
      visited[ii] = false;
      subvec.pop_back();
    }
    return;
  }

  inline short serialize(std::vector<int> &vec)
  {
    short code{ 0 };
    for (auto const &idx : vec) {
      code |= (1 << idx);
    }
    return code;
  }
};

Complexity

• Time complexity: O(N2^N), 2^N from the enumaration of all possibilities, the scalar N is from each enumeration requires of looping over the subvec to serialize itself into a short (as the maximum of subvec length is N)
• Space complexity: O(2^N) the hashtable for recording the subvector identities

[ginnydyy]

Problem

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

Notes

• Bit manipulation
  • Use n binary bits to represent the selection of n numbers, 1 is selected, 0 is not selected.
  • Outer for loop to move the mask from 0 to 2^n - 1. Inner for loop to put or not put the number at the current index based on the mask bits.
  • Clear the current selected list before the inner for loop. Add the current selected list to the result list after the inner for loop.
• Backtracking
  • Select the number at the current index, add the number at the current index to the current list, recursively to process the next index.
  • Not select the number at the curent index, backtrack the selected number, recursively to process the next index.
  • When the current index reaches the length of the number array, put the current list to the result list.

Solution

• Bit manipulation

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

• Backtrack

  class Solution {
  public List<List<Integer>> subsets(int[] nums) {
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> curList = new ArrayList<>();
      helper(nums, 0, curList, res);
      return res;
  }
  
  private void helper(int[] nums, int start, List<Integer> curList, List<List<Integer>> res){
      if(start == nums.length){
          res.add(new ArrayList<>(curList)); // deep copy
          return;
      }
  
      // select the number at the current index
      curList.add(nums[start]);
      helper(nums, start + 1, curList, res);
  
      // backtrack and not select the number at the current index
      curList.remove(curList.size() - 1);
      helper(nums, start + 1, curList, res);
  }
  }

Complexity

• Time: O(n * 2^n), there are total 2^n unique subsets, to form each subset, it costs O(n) time. n is the length of the given number array.
• Space: O(n), the extra space required is for the current list for each subset case.

[CoreJa]

思路

题目要求枚举列表所有可能的子集，思路之一就是枚举，因为所有子集的个数为2^len(nums)，所以i从0到2^len(nums)，把i看作二进制解读，0表示该位没有数，1表示该位有数即可。

另一个思路类似，对于一个已经枚举了列表[1,2,3]所有子集的results而言，如果想再加上4，那么只用考虑所有已存在的results全部都带上4和全部都不带4两种情况即可；即[i + [num] for i in results]是所有results带上了4，而不带4就是results本身，二者相加就是结果

代码

class Solution:
    def subsets1(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for i in range(1 << len(nums)):
            tmp = []
            index = 0
            while i:
                if i & 1:
                    tmp.append(nums[index])
                index += 1
                i >>= 1
            ans.append(tmp)
        return ans

    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))]

    def subsets3(self, nums: List[int]) -> List[List[int]]:
        results = [[]]
        for num in nums:
            results += [i + [num] for i in results]
        return results

    def subsets4(self, nums: List[int]) -> List[List[int]]:
        return reduce(lambda res, num: res + [i + [num] for i in res], nums, [[]])

复杂度

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

[ZacheryCao]

Idea:

Bitmask. A binary value to represent the element we choose in the subset (1 for choosing, 0 for not choosing).

Code:

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

Coplexity:

Time: O(N 2^N). Since the bitmask has N length, it has 2^N possible values. For each value from 2^N values, we need to right move N bits of the current value to check the selectd nums[i] Space: Time: O(N 2^N).

[yuxiangdev]

 public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int[] nums, int start, List<Integer> subset, List<List<Integer>> res) {
        res.add(new ArrayList<>(subset));

        for (int i = start; i < nums.length; i++) {
            subset.add(nums[i]);
            dfs(nums, i + 1, subset, res);
            subset.remove(subset.size() - 1);
        }
    }

Time O(2 ^ n)

Space O(2 ^ n)

[yingliucreates]

link:

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

代码 Javascript

const subsets = function(nums) {
    let result = [[]];

    function backtrack(first, current) {

    for (let i = first; i < nums.length; i++) {
        current.push(nums[i]);

        result.push([...current]);

        backtrack(i + 1, current);

        current.pop();
    }
}

    backtrack(0, []);
    return result
};

[wangzehan123]

Java Code:

class Solution {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();

        if (nums == null) {
            return results;
        }

        if (nums.length == 0) {
            results.add(new ArrayList<Integer>());
            return results;
        }

        Arrays.sort(nums);
        helper(new ArrayList<Integer>(), nums, 0, results);
        return results;
    }

    // 递归三要素
    // 1. 递归的定义：在 Nums 中找到所有以 subset 开头的的集合，并放到 results
    private void helper(ArrayList<Integer> subset,
                        int[] nums,
                        int startIndex,
                        List<List<Integer>> results) {
        // 2. 递归的拆解
        // deep copy
        // results.add(subset);
        results.add(new ArrayList<Integer>(subset));

        for (int i = startIndex; i < nums.length; i++) {
            // [1] -> [1,2]
            subset.add(nums[i]);
            // 寻找所有以 [1,2] 开头的集合，并扔到 results
            helper(subset, nums, i + 1, results);
            // [1,2] -> [1]  回溯
            subset.remove(subset.size() - 1);
        }

        // 3. 递归的出口
        return;
    }
}

[RocJeMaintiendrai]

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        helper(res, new ArrayList<>(), nums, 0);
        return res;
    }

    private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int idx) {
        res.add(new ArrayList<>(list));
        for(int i = idx; i < nums.length; i++) {
            list.add(nums[i]);
            helper(res, list, nums, i + 1);
            list.remove(list.size() - 1);
        }

    }
}

复杂度分析

时间复杂度

O(2^n)

空间复杂度

O(n)

[laofuWF]

# backtrack

# time: O(2^N)
# space: O(N)

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

    def backtrack(self, nums, res, curr_list):
        res.append(curr_list.copy())
        if not nums:
            return

        for i, n in enumerate(nums):
            curr_list.append(n)
            self.backtrack(nums[i + 1:], res, curr_list)
            curr_list.pop()

[Laurence-try]

思路

backtracking

代码

使用语言：Python3:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(index, curr):
            if len(curr) == i:
                sub.append(curr[:])
                return
            for j in range(index, n):
                curr.append(nums[j])
                backtracking(j + 1, curr)
                curr.pop()

        sub = []
        n = len(nums)
        curr = []
        for i in range(n + 1):
            backtracking(0, curr)

        return sub

复杂度分析 时间复杂度：O(n* 2^n) 空间复杂度：O(n)

[tongxw]

思路

位运算，每个数字可以选也可以不选，所以子集最多有2^n个，所以枚举[0...2^n-1]的所有数字，用它们的二进制位作为选或者不选的标记，最后组成答案。

代码

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

            ans.add(subset);
        }

        return ans;
    }

}

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

[yan0327]

思路： 啊！啊！啊！ 前几天做过，今天思路又忘记了。 回顾： dfs深度搜索，每次都 copy添加到输出out里面， 从起始节点开始遍历，list加元素，可加可不加，加了做一次dfs，出来之后再去掉

func subsets(nums []int) [][]int {
    out := [][]int{}
    var dfs func(start int, list []int)
    dfs = func(start int,list []int){
        p := make([]int,len(list))
        copy(p,list)
        out = append(out,p)
        for j:=start;j<len(nums);j++{
            list = append(list,nums[j])
            dfs(j+1,list)
            list = list[:len(list)-1]
        }
    }
    dfs(0,[]int{})
    return out
}

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

[wenlong201807]

代码块

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

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[Tao-Mao]

Idea

Recursion

Code

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

    public void helper(int[] nums, List<Integer> cur, int index) {
        res.add(new ArrayList<>(cur));
        for (int i = index; i < nums.length; i++) {
            cur.add(nums[i]);
            helper(nums,cur,i+1);
            cur.remove(cur.size()-1);
        }
    }
}

Complexity

Time O(2^n*n)

Space O(2^n*n))

[ymkymk]

思路

回溯算法

代码

``

class Solution {

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

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            backtrack(j + 1, nums, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

复杂度分析

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

空间复杂度：O(n)

[chaggle]

---

title: "Day 72 78. 子集" date: 2021-11-20T09:08:01+08:00 tags: ["Leetcode", "c++", "traceback"] categories: ["91-day-algorithm"] draft: true

---

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

题目思路

• 1、本题目若是求子集个数该多好，直接全排列即可，可惜是求每一个对应的子集。
• 2、利用两个数组，一个存最后的答案，一个用来做缓存数组，两个dfs的意思为，先加入所有的子元素，然后一个一个剔除，剔除一个元素，最终的答案数组将其存入。
• 3、最后34天要考研了，写的会比较紧张。

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

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0, nums);
        return ans;
    }

    void dfs(int i, vector<int>& nums) {
        int n = nums.size();
        if (i == n) {
            ans.push_back(tmp);
            return;
        }
        tmp.push_back(nums[i]);
        dfs(i + 1, nums);
        tmp.pop_back();
        dfs(i + 1, nums);
    }

};

复杂度

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

• 空间复杂度：O(n)

[nonevsnull]

思路

• 拿到题的直觉解法
  • backtrack可以直接做；
  • bit这个思路真是很神奇；
  • 性质：利用1 << i可以挪位，利用&可以比较当前位置和目标是否匹配都为1；
  • 性质：利用每个元素的选与不选两种状态，2^N即为所有可能性

AC

代码

//回溯
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        for(int i = 0;i <= nums.length;i++){
            List<Integer> subset = new ArrayList<>();
            backtrack(nums, i, subset, 0);
        }
        return res;
    }

    public boolean backtrack(int[] nums, int size, List<Integer> subset, int start){
        if(subset.size() == size){
            res.add(new ArrayList(subset));
            return true;
        }

        for(int i = start;i < nums.length;i++){
            subset.add(nums[i]);
            backtrack(nums, size, subset, i+1);
            subset.remove(subset.size() - 1);
        }
        return false;
    }
}

//bit操作很神奇
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int start = 0, end = (int)Math.pow(2, nums.length);

        for(int sign = start;sign < end;sign++){
            List<Integer> set = new ArrayList<>();

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

        return res;
    }
}

复杂度

time: O(N * 2^N) space: O(N)

[kendj-staff]

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        search(nums, res, path, 0);
        return res;
    }
    public void search(int[] nums, List<List<Integer>> res, List<Integer> path, int index) {
        res.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            search(nums, res, path, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

[user1689]

题目

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

思路

bitManipulation

python3

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

        # time n * 2**n
        # space n
        res = []
        sum = 1 << len(nums)
        # 2**n
        for i in range(0, sum):
            tmp = []
            # n
            for j in range(0, len(nums)):
                if (( i >> j ) & 1) == 1:
                    tmp.append(nums[j])
            res.append(tmp)
        return res

复杂度分析

• time n*2**n
• space n

相关题目

1. 待补充

[bingyingchu]

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

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

[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

[laurallalala]

代码

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def helper(nums, i, cur, res):
            if i >= len(nums):
                res.append(cur)
                return
            helper(nums, i+1, cur+[nums[i]], res)
            helper(nums, i+1, cur, res)

        res = []
        helper(nums, 0, [], res)
        return res

复杂度

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

[pan-qin]

Idea:

Each num can be selected or unselected. So we can use a binary bitmask to map which number is selected.

Complexity:

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

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

[zjsuper]

Iterative methods time(N^2)

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

[joeytor]

思路

遍历所有可能性 [0, 1<<l - 1]

每次如果 i & (1<<j) 代表这一位的 i 是 1, 那么这个 list 要取这一位数, 将这一位数添加到现在都 list tmp 中

遍历结束后将 tmp 加入 res 数组中

最后返回 res 数组

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

        res = []
        l = len(nums)

        for i in range(1<<l):
            tmp = []
            for j in range(l):
                if i & (1<<j):
                    tmp.append(nums[j])
            res.append(tmp)
        return res

复杂度

时间复杂度: O(n * 2^n) 一共 2^n 个不同的状态, 每次构造一个状态的复杂度是 O(n)

空间复杂度: O(n) 每次 tmp 数组的空间复杂度是 O(n)

[thinkfurther]

思路

使用BFS，每次把一位加入到所有的已有list

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [[]]
        for num in nums:
            for i in range(len(result)):
                temp = result[i][:]
                temp.append(num)
                result.append(temp)

        return result

复杂度

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

空间复杂度: O(N)

[ZJP1483469269]

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<LinkedList<Integer>> dq = new LinkedList<>();
        LinkedList<Integer> ls = new LinkedList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0 ;i < nums.length ;i++){
            map.put(nums[i],i);
        }
        dq.offer(ls);
        while(!dq.isEmpty()){
            LinkedList<Integer> ol = dq.poll();
            res.add(ol);
            for(int i = ol.size()==0 ? 0 : map.get(ol.getLast())+1; i < nums.length; i++){
                LinkedList<Integer> list = new LinkedList<>(ol);
                list.add(nums[i]);
                dq.offer(list);
            }
        }
        return res;
    }
}

[hwpanda]

不会回溯解法

var subsets = function(nums) {
  const result = [[]]

  for (const x of nums) {
    result.push(...result.map(subset => subset.concat([x])))
  }

  return result
};

[ai2095]

78. Subsets

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

Topics

• backtracking

• 思路

  backtracking

代码 Python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(k, first = 0,  curr = []):
            nonlocal n, output
            # if the combination is done
            if len(curr) == k:  
                output.append(curr[:])
                return

            for i in range(first, n):
                # add nums[i] into the current combination
                curr.append(nums[i])
                # use next integers to complete the combination
                backtrack(k, i + 1, curr)
                # backtrack
                curr.pop()

        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack(k=k, first=0, curr=[])
        return output

复杂度分析

DP 时间复杂度： O(NLogN)
空间复杂度：O(N)

[XinnXuu]

思路

假设有N个元素，则有2^N种状态，每个状态可用1bit表示。

代码

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

复杂度

• 时间复杂度：O(N * 2^N)，共有2^N种状态，每种状态的构建需要O(N)。
• 空间复杂度：O(N), 为临时数组list所需空间，不包括返回结果res的空间。

[ghost]

题目

78. Subsets

代码

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

        for num in nums:
            for i in range(len(res)):
                res.append(res[i] + [num])

        return res

复杂度

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

[yibenxiao]

【Day 72】78. 子集

代码

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

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

[falconruo]

代码(C++):

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

        for (int num : nums) {
            int len = res.size();

            for (int i = 0; i < len; ++i) {
                res.push_back(res[i]);
                res.back().push_back(num);
            }
        }

        return res;
    }
};

[chenming-cao]

解题思路

位运算。长度为n的无重复元素数组的所有子集数为2^n。我们可以用0到2^n - 1的二进制形式来表示不同子集。每一个二进制数从低位到高位分别表示nums[0]到nums[n - 1]在子集中的情况，我们检查对应数位是否为1，如果为1则放到子集中，最后返回子集的list即可。

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // total number of all possible subsets is 2^len
        for (int i = 0; i < (int) Math.pow(2, len); i++) {
            // use a binary number to represent whether the number in this position
            // is in the list
            // check each digit and put the corresponding number in the result list
            List<Integer> set = new ArrayList<>();
            for (int j = 0; j < len; j++) {
                // the digit in position j starting from LSD is 1
                // meaning nums[j] is in the subset
                if (((i >> j) & 1) == 1) {
                    set.add(nums[j]);
                }
            }
            res.add(set);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(2^n * n)，n为数组长度
• 空间复杂度：O(1)

[learning-go123]

思路

• 回溯

代码

• 语言支持：Go

Go Code:

func subsets(nums []int) [][]int {
    var res [][]int
    res = append(res, []int{})
    var f func(int, []int)
    f = func(start int, c []int) {
        if start >= len(nums) {
            return
        }
        for i:=start;i<len(nums);i++ {
            c = append(c, nums[i])
            tmp := make([]int, len(c))
            copy(tmp, c)
            res = append(res, tmp)
            f(i+1, c)
            c = c[:len(c)-1]
        }
    }

    f(0, []int{})
    return res
}

复杂度分析

令 n 为数组长度。

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

[jiahui-z]

思路: backtracking

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

        compose(result, new ArrayList<Integer>(), nums, 0);

        return result;
    }

    private void compose(List<List<Integer>> result, List<Integer> list, int[] nums, int index) {
        result.add(new ArrayList<>(list));
        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]); 
            compose(result, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

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

[Francis-xsc]

思路

位运算枚举

代码

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

复杂度分析

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

[mannnn6]

代码

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

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            backtrack(j + 1, nums, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

复杂度

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