全组合

问题描述

这道题是 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 题的代码新增的行

解法三：回溯

和全排列（包含重复元素）的思路相同，只需在每轮递归时不重复选择相同的元素即可：

  1. 第一种方法：将原数组排序，每层递归中，相邻的相同元素，只选择第一个（不能只选择最后一个）。这其实和解法一的思路类似，即保证“相邻的相同元素，只能连续选择”
  2. 第二种方法：将原数组排序，是使用一个哈希表记录本轮递归过程中已经选择过的元素，不再重复选择
为什么“相邻的相同元素，只选择第一个，不能只选择最后一个”？

求全排列的时候，我们也用了类似的方法来去重。但是那篇文章中，只选择第一个，或只选择最后一个，都可以。为什么这里不行呢？

因为全排列的题解中，使用 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 题的代码新增的行

结语

本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解，一起交流，共同进步！

附录

copy：

func copy (nums []int) []int {
    res := make([]int ,len(nums))
    for i, v := range nums {
        res[i] = v
    }
    return res
}