排列 / 组合 / 子集
形式一、元素无重不可复选，即 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 层的节点值即可
func backtrack(nums []int, k int) { // base case，到达第 k 层，收集节点的值 if len(track) == k { // 第 k 层节点的值就是大小为 k 的排列 res = append(res, append([]int(nil), track...)) return } // 回溯算法标准框架 for i := 0; i < len(nums); i++ { // ... backtrack(nums, k) // ... } }
元素可重不可复选
[子集] LC 90. Subsets II 子集 II
https://leetcode.com/problems/subsets-ii
和元素不可重的区别：需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过
func subsetsWithDup(nums []int) (result [][]int) { sort.Ints(nums) 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++ { if i > start && nums[i] == nums[i-1] { continue } num := nums[i] prev = append(prev, num) backtrack(i+1) prev = prev[:len(prev)-1] } } backtrack(0) return result }
[组合] LC 40. Combination sum II 组合总和 II
https://leetcode.com/problems/combination-sum-ii/description/
func combinationSum2(candidates []int, target int) (result [][]int) { sort.Ints(candidates) var prev []int var prevSum int var backtrack func(start int) backtrack = func(start int) { if prevSum == target { result = append(result, append([]int(nil), prev...)) } if prevSum >= target { return } for i := start; i < len(candidates); i++ { if i > start && candidates[i] == candidates[i-1] { continue } prev = append(prev, candidates[i]) prevSum += candidates[i] backtrack(i+1) prev = prev[:len(prev)-1] prevSum -= candidates[i] } } backtrack(0) return }
[排列] LC 47. 全排列 II
https://leetcode.com/problems/permutations-ii/description/
标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。
那么反映到代码上，你注意看这个剪枝逻辑：
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { // 如果前面的相邻相等元素没有用过，则跳过 continue; } // 选择 nums[i]
当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。
func permuteUnique(nums []int) (result [][]int) { used := make([]bool, 9) prev := make([]int, 0, 8) sort.Ints(nums) 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 i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue } if used[i] { continue } prev = append(prev, num) used[i] = true backtrack() prev = prev[:len(prev)-1] used[i] = false } } backtrack() return }
另一种剪枝思路
func permuteUnique(nums []int) (result [][]int) { used := make([]bool, 9) prev := make([]int, 0, 8) sort.Ints(nums) var backtrack func() backtrack = func() { if len(prev) == len(nums) { result = append(result, append([]int(nil), prev...)) return } prevNum := 1024 for i := 0; i < len(nums); i++ { num := nums[i] if used[i] || num == prevNum { continue } prev = append(prev, num) used[i] = true prevNum = num backtrack() prev = prev[:len(prev)-1] used[i] = false } } backtrack() return }
元素无重可复选
[组合/子集] LC 39. Combination Sum 组合总和
https://leetcode.com/problems/combination-sum/description/
func combinationSum(candidates []int, target int) (result [][]int) { var prev []int var prevSum int var backtrack func(start int) backtrack = func(start int) { if prevSum == target { result = append(result, append([]int(nil), prev...)) } if prevSum >= target { return } for i := start; i < len(candidates); i++ { prev = append(prev, candidates[i]) prevSum += candidates[i] backtrack(i) prev = prev[:len(prev)-1] prevSum -= candidates[i] } } backtrack(0) return }
[排列]
标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。
func permuteRepeat(nums []int) [][]int { var res [][]int var track []int backtrack(nums, &res, track) return res } // 回溯算法核心函数 func backtrack(nums []int, res *[][]int, track []int) { // base case，到达叶子节点 if len(track) == len(nums) { // 收集叶子节点上的值 tmp := make([]int, len(track)) copy(tmp, track) *res = append(*res, tmp) return } // 回溯算法标准框架 for i := 0; i < len(nums); i++ { // 做选择 track = append(track, nums[i]) // 进入下一层回溯树 backtrack(nums, res, track) // 取消选择 track = track[:len(track)-1] } }