Week 47 @ 2024 算法周记【回溯 - 排列/组合/子集】
- Bryan
- 1 排列 / 组合 / 子集
- 1.1 元素无重不可复选
- 1.1.1 [子集] LC 78. Subsets 子集
- 1.1.2 [组合] LC 77. Combinations 组合
- 1.1.3 [排列] LC 46. Permutations 全排列
- 1.1.3.1 扩展：只有 k 个元素的排列（不是全排列）
- 1.2 元素可重不可复选
- 1.3 元素无重可复选
- 1.3.1 [组合/子集] LC 39. Combination Sum 组合总和
- 1.3.2 [排列]
- 1.1 元素无重不可复选
排列 / 组合 / 子集
形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。
以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。
形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。
以组合为例，如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。
形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。
以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]。
当然，也可以说有第四种形式，即元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。
上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。
元素无重不可复选
[子集] LC 78. Subsets 子集
func subsets(nums []int) (result [][]int) {
var prev []int
var backtrack func(start int)
backtrack = func(start int) {
result = append(result, append([]int(nil), prev...))
for i := start; i < len(nums); i++ {
prev = append(prev, nums[i])
backtrack(i + 1)
prev = prev[:len(prev)-1]
}
}
backtrack(0)
return
}[组合] LC 77. Combinations 组合
组合和子集是一样的：大小为 k 的组合就是大小为 k 的子集。
func combine(n int, k int) (result [][]int) {
var prev []int
var backtrack func(start int)
backtrack = func(start int) {
if len(prev) == k {
result = append(result, append([]int(nil), prev...))
return
}
for i := start; i <= n; i++ {
prev = append(prev, i)
backtrack(i+1)
prev = prev[:len(prev)-1]
}
}
backtrack(1)
return
}[排列] LC 46. Permutations 全排列
func permute(nums []int) (result [][]int) {
used := make(map[int]bool, 6)
var prev []int
var backtrack func()
backtrack = func() {
if len(prev) == len(nums) {
result = append(result, append([]int(nil), prev...))
return
}
for i := 0; i < len(nums); i++ {
num := nums[i]
if used[num] {
continue
}
prev = append(prev, num)
used[num] = true
backtrack()
prev = prev[:len(prev)-1]
delete(used, num)
}
}
backtrack()
return
}扩展：只有 k 个元素的排列（不是全排列）
改下 backtrack 函数的 base case，仅收集第 k 层的节点值即可
元素可重不可复选
[子集] LC 90. Subsets II 子集 II
和元素不可重的区别：需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过
[组合] LC 40. Combination sum II 组合总和 II
[排列] LC 47. 全排列 II
标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。
那么反映到代码上，你注意看这个剪枝逻辑：
当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。
另一种剪枝思路
元素无重可复选
[组合/子集] LC 39. Combination Sum 组合总和
[排列]
标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。