chapter_backtracking/subset_sum_problem/

[giscus[bot]]

chapter_backtracking/subset_sum_problem/

在动画与代码中掌握数据结构与算法

https://www.hello-algo.com/chapter_backtracking/subset_sum_problem/

[zhuasdfg]

实在是太有石粒辣，感觉这种问题的难点在于剪枝操作怎么写，遍历递归前需要提前考虑的东西很多

[CXW20001]

我突然想到，最后一题，如果要求元素只能被选择一次，既然可以排序，那何不直接先去重，再回溯，岂不更秒。哈哈哈

[krahets]

@CXW20001 不可以哦，可以试一下看看有什么区别

[DXShelley]

根本不是人能想出来的，一环套一环，四环又四环，四环外边是五环。
《新五环之歌》》

[naivewolf-git]

重复元素的情况，剪枝四的 i > start 是不是应该改为 i > 0 啊，不然无法剪枝n个元素之和等于目标值的情况。
测试用例：
输入: nums={3,3,4,3,3,5,5,4,5}; target=12;
输出: [[3, 3, 3, 3], [3, 4, 5]]

还有个疑问是可以排序时去重代替剪枝四吗？

[krahets]

Hi，这个答案看起来是正确的，为什么需要剪枝“n 个元素之和等于目标值的情况”呢？（每一个 3 都是“不同”的元素）

题目要求“每个元素只能被选择一次”，而非“每种值的元素只能被选择一次”。如果是后者，则可以在数组排序时去重。

[naivewolf-git]

概念混淆了，感谢

[caticat]

i > start和i > 0的问题还是不太理解.
为什么这里可以用start呢?
如果start位置和start-1的值是一样的情况,会不会有问题?

[chenghui-ch]

start就相当于每次循环的0吧。
这个题不就是判断start和start-1值一样就跳过吗，为啥会有问题🤣

[muzishuiji]

subset_sum_ii.js
这部分代码里的

// 进行下一轮选择
backtrack(state, target - choices[i], choices, i + 1, res);

需要调整为： i+1 --> i ，不然不满足每个元素可被选取多次的条件～

[krahets]

这道题规定“每个元素只可被选择一次”。

[Mingquan-cloud]

请教，13.3.2中->“实现方式比较巧妙：由于数组是已排序的，因此相等元素都是相邻的”，题目没有说是给定有序数组nums啊？为什么默认就以有序数组来处理了呢？

[Mingquan-cloud]

好吧，看到这段了，偷偷对nums进行排序了。明白了
/* 求解子集和 II */
vector<vector> subsetSumII(vector &nums, int target) {
vector state; // 状态（子集）
sort(nums.begin(), nums.end()); // 对 nums 进行排序

[pythonberg1997]

关于重复情况的剪枝4，其实跟全排列问题中的 duplicated 哈希表起到了相同的作用吧，所以代码也可以这样写：

def backtrack(
    state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]
):
    """回溯算法：子集和 II"""
    # 子集和等于 target 时，记录解
    if target == 0:
        res.append(list(state))
        return
    # 遍历所有选择
    # 剪枝二：从 start 开始遍历，避免生成重复子集
    # 剪枝三：从 start 开始遍历，避免重复选择同一元素
    duplicated = set[int]()
    for i in range(start, len(choices)):
        # 剪枝一：若子集和超过 target ，则直接结束循环
        # 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if target - choices[i] < 0:
            break
        # 剪枝四：如果该元素重复，跳过
        if choices[i] in duplicated:
            break
        # 尝试：做出选择，更新 target, start
        state.append(choices[i])
        # 进行下一轮选择
        backtrack(state, target - choices[i], choices, i + 1, res)
        # 回退：撤销选择，恢复到之前的状态
        state.pop()

这样可以省去对数组进行排序。我理解的对吗？

[pythonberg1997]

漏了 duplicated.add(choices[i])

[pythonberg1997]

啊好像不行，比那种全排列的情况更复杂

[chen-xiao-yu]

按道理是可以的吧，相当于就是剪掉和他一样的兄弟节点嘛，例题里面是排了序的，可以用那种方式，如果没排序，不就应该用你说这种方式么。

[zqzwj]

重复元素应该是continue而不是break，数组中重复元素后面的其它数还能继续选

[ttppss]

考虑全排列的情况下，我这种改法是否会有问题？和原始的代码只有一个 slicing 的区别。

def backtrack(state, target, choices, res):
    if sum(state) == target:
        res.append(list(state))
        return

    for i, choice in enumerate(choices):
        if sum(state) < target:
            state.append(choice)
            backtrack(state, target, choices[i:], res)
            state.pop()

[krahets]

用 slicing 也可以的，这是 Python 这类语言的语法糖优势。不过 slicing 会额外创建一个新数组

[likz1994]

个人愚见：
13.3.1题目：“给定数组无重复元素，每个元素可以被选取多次”；

13.3.2题目：“给定数组包含重复元素，每个元素只可被选择一次”；

是否中间在增加一个案例：
13.3.X题目：“给定数组无重复元素，每个元素只可被选择一次”；
这样 就每次控制一个 变化量，这样更加 方便理解。这要求是不是有点过分啦 哈哈哈哈

[hfrangon]

把中间调用的 backtrack(state, target - choices[i], choices, i, res); 这句中传入i+1就好啦

[a417197457]

13.3.2 考虑重复元素的情况

[a417197457]

给定数组可能包含重复元素，每个元素只可被选择一次。
如果4,4,5 target为8。 结果应该是4,4
但是上面的解法跳过了4,4 这种可能？

[krahets]

不会跳过这种可能呀，测了一下：

输入数组 nums = [4, 4, 5], target = 8
所有和等于 8 的子集 res = [[4, 4]]

建议前往仓库下载代码，并在本地运行。https://github.com/krahets/hello-algo

[songshengping]

老板,出书了嘛??有计划嘛??

[songshengping]

backtrack(state, target - choices[i], choices, i , res);
我把这行的 i + 1 写成 i 也没有问题.因为我就是想可以重复选择和使用.不知道这样改对不对

[songshengping]

建议大佬 把相似的leetcode题目附上,让大家去练

[krahets]

Hi，建议直接在题单上找对应分类练习：https://github.com/krahets/LeetCode-Book

[qw124341789]

感觉回溯是枚举的另一实现

[lovelock]

前面说了回溯就是一种穷举法，所以其实效率不高，只能通过剪枝来尽量提升效率。

[2022241104]

第二项代码的state.pop()换成break会更好一点吗

[2022241104]

抱歉抱歉，我想错了

[iMissZzz]

为什么13.3.2中剪枝过程能不像上一份一样用break而改用continue？

[krahets]

        # 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
        if i > start and choices[i] == choices[i - 1]:
            continue

Hi，当该剪枝触发时，右边可能还有非重复的搜索分支，因此不能直接 break 跳出，应 continue 继续 for-loop

[480284856]

在图 13-14中，感觉第三层的第一个节点不应该出现，因为在第二轮选择中，-4^应该被剪枝4去掉。

[JianhCode]

写了个自认为比较清晰的代码，如有错误，还请指正。

void backtrack(vector<int> &nums, vector<int> &current, int total, int target, vector<vector<int>> &result, int index)
{
    if (total == target)
    { // 如果当前集合之和等于目标，则将当前集合加入结果集
        result.push_back(current);
        return;
    }

for (int i = 0; i < nums.size(); ++i)
{
    if (nums[i] + total > target || i < index || nums[i] == nums[i - 1]) continue;
        // 如果超出边界、出现重复遍历以及重复元素，则跳过
    current.push_back(nums[i]);                                   // 将当前元素加入集合
    backtrack(nums, current, total + nums[i], target, result, i); // 递归调用下一层
    current.pop_back();                                           // 回溯到上一层，移除当前元素
}
}

[WUADN]

剪枝中i < index有问题，应为 i <= index；因为要不选择重复元素，要从下一个开始遍历，或者backtrack的参数index=i+1；再者，要满足同一轮不重复选择，也应为i + 1。

[moonpoet]

重复元素的情况中4种剪枝确实有点复杂，尤其是剪枝二和剪枝三很容易混淆，这两者的维度是不同的，剪枝二是最外层遍历时会逐步减少一个元素，而剪枝三则是往内层遍历时逐步减少一个元素，感觉好像抓住了重点，但是又感觉自己理解的不够深刻，还是需要多看多调试

[Rumiple]

剪枝二是backtrack(state, target - choices[i], choices, kk, res);中的kk≥i时成立，这样保证不会遍历小于自身的元素
剪枝三是backtrack(state, target - choices[i], choices, kk, res);中的kk≥i+1时成立，这样保证只会遍历比自身大的元素

[Maco1010]

和装载问题很像

[uwanny]

我的理解是这样的：
对于第一个问题：
已知原始的数组没有重复的元素，要求列表中不能有重复的组合并且可以选重复的元素，所以下一层要从索引大于等于上一层选择的位置选择。
对于第二个问题：
已知列表有重复的元素，要求列表中不能有重复的组合并且不能选重复的元素，所以下一层要从索引大于上一层选择的位置选择。但是只这样要求依然会出现重复子集的情况，比如作者给出的例子【4，5】【不同的4，5】，造成这种情况的原因是数组有重复的元素（细节我也不太清楚），所以我们要限制在同一层下一个元素不能和上一个一样，但是下一层的元素可以和上一层的一个样，只要是不同的索引。

[JameRoyar]

其实很简单 剪枝二和剪枝三 第一次看注释为什么都是start开始遍历还有两个结果的 瞬间云里雾里
其实一个是从i开始的 一个是从i+1开始的 这里是一个没有说明白的地方很容易造成误导 注释的意义应该是让代码更清晰而不是相反的
从i开始保证了不会倒回去和原来算过的元素再结合一遍
从i+1开始是把自己和自己的结合的情况剪枝掉了

[syutengu]

是的，i是下一轮选择中保留nums[i]再次被选的可能，i+1就是把nums[i]自身也一起剪掉。

[LJQ0]

可否在这请教各位佬一道算法题，之前做的没做上来，学到这想想有点像，又有点不一样
https://acexam.nowcoder.com/coding/?uid=54AB4E4B3B08F3DD&qid=10925271

[wdllmh]

应该不是，这道题如果用每个位置的回溯，感觉可能性太多了，应该是根据按位或的性质去生成最有可能的序列进行判断

[MambaFly]

相等元素既有自身和自身相等，又有排序后相邻相等元素，因此分别对应剪枝3和剪枝4

[BLackWatch1118]

简单分享下自己的理解：
不要把这个问题按照数学上的思路理解为对元素的选择，因为代码中所有的选择都是从choices数组中选取，应当把它理解为对位置的选择，也就是对[0, 1, ~, n-1]索引子集的选择。在第一个问题中重复产生的原因是所选索引子集的大小顺序不同的，所选择的索引都是一样的，所以只需要保证选择的索引为正序，就能够排除重复子集的情况。

对于第二个问题，由于已将数组排序，大小相同的元素会排列在一起，在每轮选择排除重复元素的方法是判断此选择是否与前一个元素相同，注意剪枝4判断中会有i > start 的条件是因为start是循环中选择的首个元素，它的前一个元素在上一轮中被选择过不违反每轮中不能选择重复元素的要求。每个元素只能选择一次通过限定每次调用递归函数时令start+1实现，这个就是在前一个问题下增加了下一轮不能选择自身的条件。

[ruihao-yan]

昨天晚上梦见宿管阿姨问我回溯算法，我全说上来了:D

[Asce-ops]

重复子集那里感觉解释得不太清楚，我理解应该是当做出选择 𝑥𝑖 后，设定下一轮从索引 𝑖 + 1 开始向后遍历和相等元素在每一轮中只能被选择一次共同保证不会出现重复子集

[Arman19941113]

感觉重复元素的情况解法和题意应该出现了偏差？题目是说每个元素只可被选择一次，题解是相等元素在每一轮中只能被选择一次，这道题应该是对应 LeetCode 组合总和 2 这道题，需要引入一个 visited 辅助数组来解答。

[gfzum]

这里的描述确实有些偏差，但是解法依然是 lc 组合总和2 那道题的解法。尽管在排序后，第二次遍历到相等数字会直接跳过，但是第一次遇到该数字的下次 backtrack 不会跳过和他相等的数字，所以可以保证是 “相同元素”只出现一次，“相等元素”还是会被选择到的。

[3Ajfdjsdsk2]

我个人认为没有偏差。每个元素被选择一次是指不同轮里面，也就是结果数组中不同索引不能选取source里面同一位置元素。而相等元素在每一轮中只能选择一次指的是结果数组中同一个索引对应的元素

[Arman19941113]

嗯，没啥问题，我看岔了😂

[syutengu]

学习笔记，js版

  /* k数之和，含重复元素，回溯法，可选择是否允许元素复用 */
  function k_sum_backtracking(nums, k, can_reuse = false) {
    const res = []
    const sub = []
    backtrack()
    return res

    function backtrack(j = 0) {//记录前一轮递归中指针i到达的位置，以实现剪枝不同选择顺序造成的重复子集
      const vals = new Set()//记录使用过的值，以实现剪枝元素同值造成的重复子集
      if (!k) return res.push([...sub])

      for (let i = j; i < nums.length; i++) {
        const num = nums[i]
        if (k - num < 0 || vals.has(num)) continue

        /* 进 */
        sub.push(num)
        k -= num
        vals.add(num)
        backtrack(i + !can_reuse)//后一轮递归从i（不允许复用元素时，i+1）位置开始遍历元素
        /* 退 */
        sub.pop(num)
        k += num
      }
    }
  }

[syutengu]

应该是n数之和k

[syutengu]

递归也应该用”层“而不是”轮“作为量词计数比较好吧。

[syutengu]

sub.pop(num) ❌
sub.pop() ✔

[syutengu]

和lc#18的要求搞混了，这个没有元素个数限制，所以名字就应该叫子集和subset_sum。

[huanghejian]

关于重复哪个，为什么不直接数组去重

[wdllmh]

因为直接去重的话会导致需要多个相同元素的解不能被搜到，比如[2,2,3]中找4，就需要2+2

[YiChau]

LeetCode 对应题目： 1. 无重复元素：https://leetcode.cn/problems/combination-sum/description/
2. 考虑重复元素https://leetcode.cn/problems/combination-sum-ii/