回溯算法秒杀所有排列/组合/子集问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：回溯算法秒杀所有排列/组合/子集问题

评论礼仪 见这里，违者直接拉黑。

[Days-Go-By]

强

[Simplehippo]

感谢，受益良多。提出一个前两类问题的变体: 例如无重复每元素可用N次，有重复每元素可用N次，某元素可多次使用。这些变体将其考虑展开最终应都可变为有重复每元素仅用一次。

[Wuui-97]

顶礼膜拜，太牛逼了！

[ShawnGeek]

太绝了！

[BIT-zhaoyang]

感谢大佬的文章。大佬的文章最强的地方在于，通过归纳总结框架，高度抽象出来了一类问题。比如要不要重复选，其实就取决于下一次递归是i还是i+1。很好。

关于全排列去重，个人觉得有一个更好理解的方案。按照回溯框架的思想，每次递归的时候遍历可选列表。什么时候会造成答案重复呢？在同一个位置上，同样值的元素被选了多次。比如[2, 2]，如果选了第一个2，下次还选2，就会造成重复。为了避免这个重复，可以在遍历的时候判断一下现在要选的元素是否和上一次选择过的相等。相等就跳过。伪代码如下：

for (int i = 0, last = -1; i < nums.length; ++i) {
    if (last > -1 && nums[i] == nums[last]) continue;
    if (visited[i])   continue;
    // make choice
    last = i;
    visited[i] = true;
    path.add(nums[i]);
    
    // recursive call
    recur(path, nums);
    
    // cancel choice
    visited[i] = false;
    path.removeLast();
}

[labuladong]

@BIT-zhaoyang 这个思路也不错！我的代码：

void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    // 记录之前树枝上元素的值
    // 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
    int prevNum = -666;
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (used[i]) {
            continue;
        }
        if (nums[i] == prevNum) {
            continue;
        }

        track.add(nums[i]);
        used[i] = true;
        // 记录这条树枝上的值
        prevNum = nums[i];

        backtrack(nums, track);

        track.removeLast();
        used[i] = false;
    }
}

[TimurJiangShan]

第 40 题「 组合总和 II」的backtrack在 往track里添加元素的代码是不是写错了， 应该是 track.add(nums[i]); 而不是 track.add([i]); ?

[labuladong]

@TimurJiangShan 是写错了，已修复，感谢指正

[zhyozhi]

讲的很好，点个赞！另外有两个格式的小问题，

• 1. 排队（元素可查不可复选）解法代码中，backtrack 函数调用参数数量不一致

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;

public List<List<Integer>> permuteUnique(int[] nums) {
    ...
    // 调用是传了两个参数
    backtrack(nums, track);
    ...
}
// 只有一个参数
void backtrack(int[] nums) {
      .....
}

• 2. 读者解法中，new 前后多了加粗标记 *

void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        // 这里多了*
        res.add(**new** LinkedList(track));
        return;
    }
    ....
}

[labuladong]

@zhyozhi 感谢指正，已修复~

[c2kaka]

39题给的代码没有通过case

[yuhaoban]

第39题的回溯部分应该是i而不是i +1吧？不然没法重复选择啊。一点拙见，如果不对的话希望能指正一下，谢谢大神！

class Solution:

    def __init__(self):
        self.res = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        track = []
        self.backtrack(candidates, target, 0, track, 0)
        return self.res

    def backtrack(self, candidates, target, start, track, trackSum):
        if trackSum == target:
            self.res.append(copy.deepcopy(track))
            return
        elif trackSum > target:
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            track.append(candidates[i])
            trackSum += candidates[i]
            self.backtrack(candidates, target, i, track, trackSum)
            track.pop()
            trackSum -= candidates[i]

[labuladong]

@yuhaoban 你看错了吧，我写的就是 i 不是 i + 1 啊？

[Valor-H]

例题部分写的对的，但是总结部分应该笔误写错了。

[zhongweiLeex]

216题 组合总和3
有兴趣的朋友可以继续改进，此处实在想不到如何删除个数不符合 k要求的组合，所以直接在外部对result动手脚，最后虽然是 1ms 还是只能击败 14%的人 哈哈，

class Solution {
    List<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTrack(n,k,0,1);
        Iterator<List<Integer>> iterator = result.iterator();
        while(iterator.hasNext()){
            if(iterator.next().size() != k){
                iterator.remove();
            }
        }
        return result;
    }
    private void backTrack(int target,int k,int sum,int start){
        if(sum == target){
            result.add(new LinkedList<>(track));
            return;
        }
        if(sum > target){
            return;
        }
        for(int i = start; i<= 9; i++){
            sum += i;
            k--;
            track.add(i);
            backTrack(target,k,sum,i+1);
            track.removeLast();
            k++;
            sum -= i;
        }
    }
}

[FZ20192019]

发现对于排列（元素可重不可复选）的剪枝部分，使用
if(i > 0 && nums[i] == nums[i - 1] && used[i-1])也可以通过测试，具体解释为 如果前面的相邻相等元素被用过，则跳过。 貌似更好理解些。:)

[sxcnmslll]

用过，则跳过。 貌似更好理解些

即使used[i -1] = true（添加了nums[i - 1]），也是有可能需要选择nums[i]的。

&& used[i-1])直接忽略了上述的可能性，结果可能出错

[labuladong]

@sxcnmslll @FZ20192019 其实你们的说法都不太准确，我把对 used[i-1] 的分析补充在文中了，可以看下

[forexgg]

第 47 题「 全排列 II」也可以尝试，不用used list

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path, nums):
            if not nums:
                res.append(path)
                return
            for i, num in enumerate(nums):
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                backtrack(path + [num], nums[:i] + nums[i+1:])
        
        res = []
        nums.sort()
        backtrack([], nums)
        return res

[SEU-zxj]

东哥，《排列（元素无重可复选）》这种情况下面ChatGPT翻译的CPP代码好像有些问题，它依然还是在用used数组剪枝。

[gaifanking]

关于排列有重复元素问题，为什么要使用!used[i-1]，我的一个理解是这样做到了同层剪枝，而父子结构不能剪枝。
[1,2,2'] 的一个结果1,2,2' 不能剪，因为是父子结构；而2,1,2'和2‘,, 后面的一组就可以剪掉了，因为此时同一层，没必要继续。

[xixi1998]

总结部分，形式三、元素无重可复选，在子集/组合框架模版backtrack(nums,i,track),不是i+1

[Simplehippo]

感谢，受益良多。提出一个前两类问题的变体: 例如无重复每元素可用N次，有重复每元素可用N次，某元素可多次使用。这些变体将其考虑展开最终应都可变为有重复每元素仅用一次。

[TomBlade]

请问子集（元素无重不可复选）里第17行加入路径，res.add(new LinkedList<>(track))括号里直接写track可以吗？

[TomBlade]

没通过，但请问为什么啊？

[TomBlade]

明白了，看错了track数据类型，以为是数组队列

[dusthub]

力扣上没有类似的题目，我们不妨先想一下，nums 数组中的元素无重复且可复选的情况下，会有哪些排列？

比如输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：

[
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func permuteRepeat(nums []int) [][]int {
var res [][]int
track := []int{}

// 回溯核心函数
var backtrack func(nums []int)
backtrack = func(nums []int) {
    // 如果选择的路径等于原数列长度，就收录这个排列
    if len(track) == len(nums) {
        res = append(res, append([]int(nil), track...))
        return
    }

    for i := 0; i < len(nums); i++ {
        // 如果路径中已经包含了当前选择，就跳过
        if contains(track, nums[i]) {
            continue
        }
        
        // 做选择
        track = append(track, nums[i])
        // 进入下一层回溯树
        backtrack(nums)
        // 取消选择
        track = track[:len(track)-1]
    }
}

backtrack(nums)
return res

}

// 判断一个切片中是否包含某个元素的函数
func contains(track []int, x int) bool {
for _, num := range track {
if num == x {
return true
}
}

return false

}

以下这段代码是不是多余的：
// 如果路径中已经包含了当前选择，就跳过
if contains(track, nums[i]) {
continue
}
实测去掉这个判断才能生成27种

[Letter0]

有朋友知道为什么子集/组合中的backtrack方法中参数starter赋值给i参与循环 与 排列中的backtrack方法中循环i直接赋值0，有什么区别呢？

[leejh-123]

子集/组合中，集合【1，2，3】和【1，3，2】属于同一个集合（无序性），start赋值给i是为了确定一种固定顺序，不断的往后遍历；而排列中，比如说找【1，2】的全排列，【1，2】和【2，1】属于两种，所以每次往下一层之后都要从头开始遍历，并且用used去重，当找出【1，2】后，就要找2开头的排列，那2的下一个是没有数字的，所以要从头遍历，才能找的1，1还没使用过。可能表达不清楚，希望对你有帮助！

[Letter0]

蟹蟹解释！我理解了

[Valor-H]

最后总结，第三部分元素无重可复用，组合问题中，这里代码的进入下层决策的 backtrack(i) 而不是 backtrack(i + 1)，和上面讲的不一致。

[leejh-123]

关于 子集/组合（元素可重不可复选），if(i > start && nums[i] == nums[i-1]) continue; 这里的i > start，指的是nums[i]不能是子树中的第一个子树，也就是不能是最左边那棵树，那么这里的判断指的就是：nums[i] 和 nums[i-1]相等，并且nums[i]和nums[i-1]不是父子关系，而是兄弟关系，那么就将nums[i]这条枝剪掉。只保留了第一条枝，后面相同的数字的枝都剪了。

[leejh-123]

关于 排列（元素可重不可复选）if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; 这里的剪枝，要满足的条件是：这两个数相邻，并且nums[i-1]没用过，那么只有一种情况，nums[i]和nums[i-1]是兄弟关系，不是父子关系。感觉和 子集/组合（元素可重不可复选）的剪枝一样。个人理解，欢迎指正。

[shiboys]

回溯法确实玩的很溜，总结概括除了新高度！

[hanqin5472]

太强了，跟着这篇文章刷题感觉非常nice。刚开始啥也不会，刷了几道题后后面的题几乎就能灵活运用。

[hanleilei]

其实，代码中的path/track，全部的都改成stack，一下子更容易理解了呢。

[CZT0]

40. 组合总和 II
    golang代码没有翻译哦，我给一个版本的翻译

import (
    "sort"
)

func combinationSum2(candidates []int, target int) [][]int {
    track :=[]int{}
    res := [][]int{}
    var sum int
    sort.Ints(candidates)
    var backtrack func(int)
    backtrack =func(start int){
        if sum == target {
            temp:=make([]int,len(track))
            copy(temp,track)
            res=append(res,temp)
            return
        }
        if (sum>target){
            return
        }
        for i:=start;i<len(candidates);i++{
            if i>start && candidates[i]==candidates[i-1]{
                continue
            }

            track=append(track,candidates[i])
            sum+=candidates[i]
            backtrack(i+1)
            track=track[:len(track)-1]
            sum-=candidates[i]
        }
    }
    backtrack(0)
    return res
}

[hello-bluedog]

神！！！