【LeetCode】78、90 全组合（子集）
全组合
问题描述
这道题是 LeetCode 78 题 - 子集。
从不含重复元素的 n 个元素中，选择 0~n 个元素，组成一个子集，找出所有的子集（幂集）。
解法一：二进制转换法
如果 n 个元素都不相同，可以使用二进制转换法求得所有的子集。将一个数从 0 开始，每次加 1，一直加到 $2^n-1$，其二进制表示从 000...000 到 111...111，每一位表示对应元素是否被选择。这种方法的限制是 n <= 64。
时间复杂度：$O(n×2^n)$。
空间复杂度：$O(n)$，需要一个数组临时保存每个组合，不算保存最终结果所需的空间。
func subsets(nums []int) [][]int {
res := [][]int{}
sum := 1 << len(nums) - 1
for i := 0; i <= sum; i++ {
tmp := i
cur := []int{}
for j := len(nums) - 1; j >= 0 && tmp > 0; j-- {
if tmp & 1 == 1 {
cur = append(cur, nums[j])
}
tmp >>= 1
}
res = append(res, cur)
}
return res
}
解法二：递归
对于每个元素，有「选」或者「不选」两种情况。
时间复杂度：$O(2^n)$，相当于一个 n 层的二叉树。
空间复杂度：$O(n)$，递归的最大深度，不算保存最终结果所需的空间。
代码：
var res [][]int
func subsets(nums []int) [][]int {
res = nil
dfs(0, nums, nil)
return res
}
func dfs(start int, nums []int, cur []int) {
if start >= len(nums) { // 遍历完 n 个元素，保存结果
res = append(res, copy(cur))
return
}
dfs(start+1, nums, cur) // 不选当前元素
dfs(start+1, nums, append(cur, nums[start])) // 选当前元素
}
func copy (nums []int) []int {
res := make([]int ,len(nums))
for i, v := range nums {
res[i] = v
}
return res
}
解法三：回溯
对于每个元素，有「选」或者「不选」两种情况：
- 在每一层，遍历
[start,n)的每个元素i，选择它，然后进入下一层 - 下一层只能选择
[i+1,n)之间的元素 - 从下一层返回时，取消选择
i（回溯），继续选择下一个元素 - 每次进入
dfs时，会产生一个新的结果
时间复杂度：$O(2^n)$。每次递归都会找到一个解，一共 $2^n$ 个解。
空间复杂度：$O(n)$，递归的最大深度，不算保存最终结果所需的空间。
解法二是到最后一层得到一个解，而解法三是每个节点都会得到一个解。
代码：
var res [][]int
func subsets(nums []int) [][]int {
res = [][]int{}
dfs(0, nums, nil)
return res
}
func dfs(start int, nums []int, cur []int) {
res = append(res, copy(cur)) // 每层有一个结果
for i := start; i < len(nums); i++ { // 从 start 开始遍历
cur = append(cur, nums[i]) // 选择 nums[i]
dfs(i+1, nums, cur) // 下一层从 i+1 开始遍历
cur = cur[:len(cur)-1] // 取消选择 nums[i]，回溯
}
}
解法四：逐个枚举法
将空集作为默认子集，然后逐个枚举集合中的元素。每新增一个元素，就在之前的所有子集中追加这个元素，得到新增的子集。
每新增一个元素，子集个数翻倍，因此 n 个元素的所有子集个数为 $2^n$。
时间复杂度：$O(2^n)$。每次遍历的子集个数依次为 $1,2,4,…,2^n$，套用等比数列求和公式，遍历总次数为 $O(2^n)$。
空间复杂度：$O(n^2×2^n)$。可以这样推导：每新增一个元素，子集个数翻倍，新增的子集长度也翻倍，则 n 层总的子集长度为 $\sum_{i=1}^n{(2^{i-1}×{i-1}+2^{i-1}×i)}$。括号内合为一项 $O(i×2^i)$，总的时间复杂度可表示为 $O(n^2×2^n)$。
代码：
func subsets(nums []int) [][]int {
res := [][]int{[]int{}}
for _, v := range nums {
size := len(res)
for i := 0; i < size; i++ {
newSub := copy(res[i])
newSub = append(newSub, v)
res = append(res, newSub)
}
}
return res
}
全组合（包含重复元素）
问题描述
这道题是 LeetCode 90题 - 子集-ii。
从可能包含重复元素的 n 个元素中，选择 0~n 个元素，组成一个子集，找出所有的子集（幂集）。
说明：解集不能包含重复的子集。
解法一：二进制转换法
将原来的解法调整为：先将原数组排序，然后相邻的相同元素，必须连续选择。「连续选择」保证了：若某个组合中有 k 个相同的元素，则这 k 个元素只可能通过一种方式得到。比如对于 1 1 1 2 3，假设某个组合中有 2 个 1，如果不加「连续选择」的限制，则这 2 个 1 的下标可能是 [0,1]、[0,2]、[1,2]；如果保证「连续选择」，则这 2 个 1 的下标只可能是 [0,1]。
代码：
func subsetsWithDup(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
+ sort.Ints(nums) // 先排序
res := [][]int{}
sum := 1 << uint(len(nums))
for i := 0; i < sum; i++ {
stack := []int{}
tmp := i
+ valid := true
for j := len(nums) - 1; j >= 0; j-- {
if tmp&1 == 1 {
+ if j > 0 && nums[j] == nums[j-1] && (tmp>>1)&1 == 0 {
+ valid = false
+ break
+ }
stack = append([]int{nums[j]}, stack...)
}
tmp >>= 1
}
+ if valid {
res = append(res, stack)
+ }
}
return res
}
代码中的“+”号表示这是相比于 78 题的代码新增的行
解法三：回溯
和全排列（包含重复元素）的思路相同，只需在每轮递归时不重复选择相同的元素即可：
- 第一种方法：将原数组排序，每层递归中，相邻的相同元素，只选择第一个（不能只选择最后一个）。这其实和解法一的思路类似，即保证“相邻的相同元素，只能连续选择”
- 第二种方法：将原数组排序，是使用一个哈希表记录本轮递归过程中已经选择过的元素，不再重复选择
为什么“相邻的相同元素，只选择第一个，不能只选择最后一个”？
求全排列的时候，我们也用了类似的方法来去重。但是那篇文章中，只选择第一个，或只选择最后一个，都可以。为什么这里不行呢？
因为全排列的题解中，使用 flags 数组来表示哪些元素已经被使用，防止重复使用同一个元素，因此每层递归都会从 0 开始遍历所有的元素。而在这个题解中，通过限制下层递归从 i+1 开始，来防止重复使用同一个元素。因此如果「相邻的相同元素选择最后一个」，会丢失部分解。
这里也可以使用 flags 数组来改造一下。略。
第一种方法代码：
var res [][]int
func subsetsWithDup(nums []int) [][]int {
res = nil
+ sort.Ints(nums)
dfs(0, nums, nil)
return res
}
func dfs(start int, nums []int, cur []int) {
res = append(res, copy(cur)) // 每层有一个结果
for i := start; i < len(nums); i++ { // 从 start 开始遍历
+ if i > start && nums[i] == nums[i-1] {
+ continue // 相同的值，只选择第一个，不重复选择
+ }
cur = append(cur, nums[i]) // 选择 nums[i]
dfs(i+1, nums, cur) // 下一层从 i+1 开始遍历
cur = cur[:len(cur)-1] // 取消选择 nums[i]，回溯
}
}
代码中的“+”号表示这是相比于 78 题的解法三新增的行
第二种方法也必须将数组排序，否则测试用例 [4,4,4,1,4] 会重复。代码：
class Solution {
private:
vector<vector<int>> res;
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
solve(nums, 0, vector<int>());
return res;
}
void solve(vector<int> nums, int start, vector<int> cur) {
res.push_back(cur);
set<int> visited;
for (int i = start; i < nums.size(); i++) {
if (visited.find(nums[i]) != visited.end()) continue;
visited.insert(nums[i]);
cur.push_back(nums[i]);
solve(nums, i+1, cur);
cur.pop_back();
}
}
};
解法四：逐个枚举法
将原来的解法调整为：先对数组排序，然后每新增一个元素，如果和前一个元素相同，那么只在「前一个元素新增的子集」中追加这个元素，得到新增的子集。
代码：
func subsetsWithDup(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
+ sort.Ints(nums) // 先排序
res := [][]int{[]int{}}
preSize := 0
for idx, v := range nums {
i, size := 0, len(res)
+ if idx > 0 && nums[idx] == nums[idx-1] {
+ i = preSize
+ }
for ; i < size; i++ {
newSub := copy(res[i])
newSub = append(newSub, v)
res = append(res, newSub)
}
+ preSize = size
}
return res
}
代码中的“+”号表示这是相比于 78 题的代码新增的行
附录
copy：
func copy (nums []int) []int {
res := make([]int ,len(nums))
for i, v := range nums {
res[i] = v
}
return res
}