Versions Compared

Old Version 2

changes.mady.by.user Bryan

Saved on

compared with

New Version 3

changes.mady.by.user Bryan

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Autosaved

...

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

...

元素无重不可复选

[子集] LC 78. Subsets 子集

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

Code Block
languagego
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
languagego
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
languagego
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
languagego
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
languagego