全组合

问题描述

这道题是 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
}