排列 / 组合 / 子集

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

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