LeetCode 78. 子集

发表于 更新于 分类于 Changyan： 本文字数： 523 阅读时长 ≈ 2 分钟

题目描述

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集。(解集不能包含重复的子集。)

示例：

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解法一（递归）

观察到输出集合从空集开始，依次遍历nums内的数值，每遍历一个数值，就往输出集合中加入原来的所有子集中添加当前遍历到的数值。例如，遍历到nums内的数值2，输出集合原来的子集有[]、[1]，需要往集合中添加[2]、[1,2]。使用递归实现这一过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    ans.push_back(vector<int> {});
    subsetsCore(nums, ans, 1);
    return ans;
  }

  void subsetsCore(vector<int>& nums, vector<vector<int>>& ans, int level) {
    if (level > nums.size())
      return;
    int size = ans.size();
    for (int i = 0; i < size; i++) {
      vector<int> tmp = ans[i];
      tmp.push_back(nums[level - 1]);
      ans.push_back(tmp);
    }
    subsetsCore(nums, ans, level + 1);
  }
};

解法二（回溯）

输出集合从空集开始，回溯先从nums的第一个数值1开始，依次得到[1]、[1,2]、[1,2,3]、[1,3]，然后再从nums的第二个、第三个数值开始，直到回溯结束。

回溯算法模版 
1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  vector<vector<int>> subsets(vector<int>& nums) {
    backtrace(nums, 0);
    return ans;
  }

  void backtrace(vector<int>& nums, int pos) {
    ans.push_back(path);
    for (int i = pos; i < nums.size(); i++) {
      path.push_back(nums[i]);
      backtrace(nums, i + 1);
      path.pop_back();
    }
  }

 private:
  vector<vector<int>> ans;
  vector<int> path {};
};

解法三（位运算）

子集的所有情况其实可以用n位的二进制（n 为 nums.size()），例如上面的例子可以用3位二进制表示所有情况，000、001、010、011、100、101、110、111。不过如果nums的size大于一定数值时会溢出（例如int类型不能超过32位），可以使用bitset。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    int N = 1 << nums.size();
    for (int i = 0; i < N; i++) {
      vector<int> tmp;
      for (int j = 0; j < nums.size(); j++) {
        if (i & (1 << j)) {
          tmp.push_back(nums[j]);
        }
      }
      ans.push_back(tmp);
    }
    return ans;
  }
};