子集问题（LeetCode 78 90）
1 子集问题
本篇文章主要介绍了子集问题以及详细的解法。
给定一个数组求出其中所有的子集。
其中的数组，可能带重复元素，也可能不带重复元素。
有详细思路以及递归树图解，语言包括C++、Java和Go。
下面先来看看简单的版本，不带重复元素的。
2 不带重复元素的子集
题目链接。
子集的定义就是里面的元素也是另一个集合的元素，因此，有两种基本的思路。
2.1 选或不选
第一个思路是针对每个元素，可以“选”或“不选”。
具体来说，比如集合{1,2,3}，针对其中的每个元素，选择或者不选择，递归树如下：
代码如下：
class Solution {
private:
public:
vector<vector<int>> subsets(vector<int> &nums) {
// 长度
int n = static_cast<int>(nums.size());
// 存储结果
vector<vector<int>> res;
// 当前选择的元素
vector<int> cur;
auto dfs = [&](this auto &&dfs, int i) {
// i等于n时表明所有元素已经处理完成了，存储结果，然后返回
if (i == n) {
res.push_back(cur);
return;
}
// 不选
dfs(i + 1);
// 选择
cur.push_back(nums[i]);
dfs(i + 1);
// 回溯
cur.pop_back();
};
dfs(0);
return res;
}
};
2.2 枚举选择哪个
另一种思路是，枚举选择哪个，在每次递归的时候，枚举当前能选择的元素并进行选择。
也是拿{1,2,3}做例子，递归树如下：
和上面的不同，这里需要使用额外的下标去进行标识，标识当前能选择元素的集合有哪些。代码如下：
class Solution {
private:
public:
vector<vector<int> > subsets(vector<int> &nums) {
ranges::sort(nums);
// 长度
int n = static_cast<int>(nums.size());
// 存储结果
vector<vector<int> > res;
// 当前选择的元素
vector<int> cur;
auto dfs = [&](this auto &&dfs, int i)-> void {
// 存储结果，在函数进入的时候存储，这样能存储到空集，而不是push_back()之后再存储
res.push_back(cur);
// 枚举每个元素
for (int j = i; j < n; ++j) {
// 因为元素没有重复，所有元素都能选择，直接选择即可
cur.push_back(nums[j]);
// 下标加1，当前已经选择过的元素就不能在下一层再选择了
dfs(j + 1);
// 回溯
cur.pop_back();
}
};
dfs(0);
return res;
}
};
3 带重复元素的子集
题目链接。
和不带重复元素的一样，也是有两种思路。
3.1 选或不选
和之前的问题不同，多了重复的元素，这样会造成一个问题就是，如果直接像之前那样选或者不选某个元素，会有重复的子集。
例如，对于{1,2,2}，在选了{1}的情况下，如果：
- 选第一个2不选第二个2，会得到
{1,2} - 选第二个2不选第一个2，也会得到
{1,2}
所以需要一种方法去判断什么时候可以选2，以及选第几个2。
为什么上面的例子会出现重复的{1,2}？是因为选的2重复了。
为什么选的2会重复？当排序之后，在没有选择前面第一个2的情况下，选择了第二个2，这样就造成了重复。如果有多个，那么结论就是在没有选择第一个2的情况下，不能选择第二个2，第三个2，…第n个2。
所以做法就是，如果已经选择了前面的2，把剩下的2都跳过。更一般地，如果选择了前面的x，就把剩下的x全部都跳过。
递归树：
代码：
class Solution {
private:
public:
vector<vector<int> > subsetsWithDup(vector<int> &nums) {
// 先排序，方便后续处理
ranges::sort(nums);
// 长度
int n = static_cast<int>(nums.size());
// 存储结果
vector<vector<int> > res;
// 当前选择的元素
vector<int> cur;
auto dfs = [&](this auto &&dfs, int i)-> void {
// 处理完成，存储结果并返回
if (i == n) {
res.push_back(cur);
return;
}
int x = nums[i];
// 选
cur.push_back(x);
dfs(i + 1);
// 回溯
cur.pop_back();
// 跳过剩余的相同元素
while (i < n && nums[i] == x) {
++i;
}
// 不选
dfs(i);
};
dfs(0);
return res;
}
};
3.2 枚举选哪个
思路类似，核心也是跳过相同的元素。在当前层选择过的元素，后面不能再次选择，递归树如下：
代码如下，和不带重复元素的相比，主要不同是添加了排序和nums[j] != nums[j-1]的去重处理。
class Solution {
private:
public:
vector<vector<int> > subsetsWithDup(vector<int> &nums) {
// 先排序，方便后续处理
ranges::sort(nums);
// 长度
int n = static_cast<int>(nums.size());
// 存储结果
vector<vector<int> > res;
// 当前选择的元素
vector<int> cur;
auto dfs = [&](this auto &&dfs, int i)-> void {
// 存储结果
res.push_back(cur);
// 枚举选哪个
for (int j = i; j < n; ++j) {
// j==i表示是第一个，可以选择
// nums[j] != nums[j-1]表示和上一个元素不一样的，才能选择，也就是跳过相同的元素，改成nums[j] > nums[j-1]也可以
if (j == i || nums[j] != nums[j - 1]) {
// 选
cur.push_back(nums[j]);
dfs(j + 1);
// 回溯
cur.pop_back();
}
}
};
dfs(0);
return res;
}
};
4 如果还有问题
如果还有问题，建议通过本地调试观察每一个递归的输入输出来构建下脑海中的递归树。
5 其他语言版本——Java
5.1 不带重复元素-选或不选
import java.util.*;
public class Solution {
private final List<List<Integer>> res = new ArrayList<>();
private int n;
private int[] nums;
private final LinkedList<Integer> cur = new LinkedList<>();
private void dfs(int i) {
if (i == n) {
res.add(new ArrayList<>(cur));
return;
}
dfs(i + 1);
cur.addLast(nums[i]);
dfs(i + 1);
cur.pollLast();
}
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
this.n = nums.length;
dfs(0);
return res;
}
}
5.2 不带重复元素-枚举选哪个
import java.util.*;
public class Solution {
private final List<List<Integer>> res = new ArrayList<>();
private int n;
private int[] nums;
private final LinkedList<Integer> cur = new LinkedList<>();
private void dfs(int i) {
res.add(new ArrayList<>(cur));
for (int j = i; j < n; j++) {
cur.addLast(nums[j]);
dfs(j + 1);
cur.pollLast();
}
}
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
this.n = nums.length;
dfs(0);
return res;
}
}
5.3 重复元素-选或不选
import java.util.*;
public class Solution {
private final List<List<Integer>> res = new ArrayList<>();
private int n;
private int[] nums;
private final LinkedList<Integer> cur = new LinkedList<>();
private void dfs(int i) {
if (i == n) {
res.add(new ArrayList<>(cur));
return;
}
int x = nums[i];
cur.addLast(x);
dfs(i + 1);
cur.pollLast();
while (i < n && nums[i] == x) {
++i;
}
dfs(i);
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
this.n = nums.length;
dfs(0);
return res;
}
}
5.4 重复元素-枚举选哪个
import java.util.*;
public class Solution {
private final List<List<Integer>> res = new ArrayList<>();
private int n;
private int[] nums;
private final LinkedList<Integer> cur = new LinkedList<>();
private void dfs(int i) {
res.add(new ArrayList<>(cur));
for (int j = i; j < n; j++) {
if (j == i || nums[j] > nums[j - 1]) {
cur.addLast(nums[j]);
dfs(j + 1);
cur.pollLast();
}
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
this.n = nums.length;
dfs(0);
return res;
}
}
6 其他语言版本——Go
6.1 不带重复元素-选或不选
func subsets(nums []int) [][]int {
res, cur, n := make([][]int, 0), make([]int, 0), len(nums)
var dfs func(i int)
dfs = func(i int) {
if i == n {
curCopy := make([]int, len(cur))
copy(curCopy, cur)
res = append(res, curCopy)
return
}
dfs(i + 1)
cur = append(cur, nums[i])
dfs(i + 1)
cur = cur[:len(cur)-1]
}
dfs(0)
return res
}
6.2 不带重复元素-枚举选哪个
func subsets(nums []int) [][]int {
res, cur, n := make([][]int, 0), make([]int, 0), len(nums)
var dfs func(i int)
dfs = func(i int) {
curCopy := make([]int, len(cur))
copy(curCopy, cur)
res = append(res, curCopy)
for j := i; j < n; j++ {
cur = append(cur, nums[j])
dfs(j + 1)
cur = cur[:len(cur)-1]
}
}
dfs(0)
return res
}
6.3 重复元素-选或不选
import (
"sort"
)
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
res, cur, n := make([][]int, 0), make([]int, 0), len(nums)
var dfs func(i int)
dfs = func(i int) {
if i == n {
curCopy := make([]int, len(cur))
copy(curCopy, cur)
res = append(res, curCopy)
return
}
x := nums[i]
cur = append(cur, x)
dfs(i + 1)
cur = cur[:len(cur)-1]
for i < n && nums[i] == x {
i++
}
dfs(i)
}
dfs(0)
return res
}
6.4 重复元素-枚举选哪个
package main
import (
"sort"
)
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
res, cur, n := make([][]int, 0), make([]int, 0), len(nums)
var dfs func(i int)
dfs = func(i int) {
curCopy := make([]int, len(cur))
copy(curCopy, cur)
res = append(res, curCopy)
for j := i; j < n; j++ {
if j == i || nums[j] > nums[j-1] {
cur = append(cur, nums[j])
dfs(j + 1)
cur = cur[:len(cur)-1]
}
}
}
dfs(0)
return res
}