Week 47 @ 2024 算法周记【回溯 - 排列/组合/子集】

Owned by Bryan
Last updated: about 6 hours agoVersion comment
4 min read

排列 / 组合 / 子集

形式一、元素无重不可复选，即 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 子集

https://leetcode.com/problems/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 组合

https://leetcode.com/problems/combinations/description/

组合和子集是一样的：大小为 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 全排列

https://leetcode.com/problems/permutations/description/

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

https://leetcode.com/problems/subsets-ii

和元素不可重的区别：需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过

[组合] LC 40. Combination sum II 组合总和 II

https://leetcode.com/problems/combination-sum-ii/description/

[排列] LC 47. 全排列 II

https://leetcode.com/problems/permutations-ii/description/

标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。

那么反映到代码上，你注意看这个剪枝逻辑：

当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

另一种剪枝思路

元素无重可复选

[组合/子集] LC 39. Combination Sum 组合总和

https://leetcode.com/problems/combination-sum/description/

[排列]

标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。