Page Comparison

...

上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。

...

元素无重不可复选

[子集] LC 78. Subsets 子集

Code Block

language	go

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 的子集。

Code Block

language	go

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/

Code Block

language	go

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 层的节点值即可

Code Block

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]，则跳过

Code Block

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/

Code Block

language	go

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/

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

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

Code Block

// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}
// 选择 nums[i]

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

Code Block

language	go

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
}

另一种剪枝思路

Code Block

language	go

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/

Code Block

language	go

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 数组的剪枝逻辑就行了。

Code Block

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]
    }
}

Versions Compared

Old Version 2

New Version Current

Key

元素无重不可复选

[子集] LC 78. Subsets 子集

[组合] LC 77. Combinations 组合

[排列] LC 46. Permutations 全排列

扩展：只有 k 个元素的排列（不是全排列）

元素可重不可复选

[子集] LC 90. Subsets II 子集 II

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

[排列] LC 47. 全排列 II

元素无重可复选

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

[排列]