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]

抱歉抱歉，我想错了

[imisswx]

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

[krahets]

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

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

[wxnzb]

为什么要i>start，就跳过

[Coolllh]

这是为了防止i=0,i-1数组越界的

[hfrangon]

并没有哦 不会i >start就跳过呀 &&为1 还要考虑后面表达式的真值 所以是这一轮中除了第一个元素以外 如果后面还有跟start位置处的元素相同的就应该跳过(在同一轮中不能重复选择)

[Coolllh]

我有个建议,就是在subset_sum_ii.java这个文件里的
// 进行下一轮选择
backtrack(state, target - choices[i], choices, i + 1, res);
加上一个注解,表明这里实际上是剪枝3,把剪枝3标在for循环头上我愣了一会,感觉好像剪枝2和剪枝3的作用是一样的,后面仔细看了代码发现,剪枝3实际上是在递归中体现的

[krahets]

谢谢建议！标注在 for 上是因为实际是通过限制 for 循环的范围来实现剪枝的（避免了一部分的选择分支）。在递归调用时，我们给 start 参数传入 i+1 ，给定下一轮的剪枝范围

[CXW20001]

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

[Jinjin680]

大佬把回溯讲得好清楚！！！

[480284856]

图13-11:
三哥四哥五哥相邀开黑，但只能两两一起玩，于是三哥首先一个人玩两个角色，很快发现没法玩，于是叫上四哥玩了一局，后面又叫上五哥玩了一局，可是都输了；等到了四哥当房主时，因为觉得三哥是个坑比，四哥直接不和他玩了，于是先自己玩了一局，也发现没法玩，于是叫上五哥玩了一局；五哥发现，四哥也是个坑比，于是后面五哥自己开了个房间，不带三哥和四哥玩了，自己手脚并用都比这两个坑比强。

[480284856]

如图13-10，我们假设没有target的限制，那么这个函数将无限递归下去。首先，每个灰色节点都是一个递归的函数，比如backtrack([], 9, 0, [3,4,5], [])对应根节点（假设函数中的9没有用）,backtrack([], 9, 3, [3,4,5], []), backtrack([], 9, 4, [3,4,5], []), backtrack([], 9, 5, [3,4,5], [])分别对应第二层的三个节点. 如果我们不对choice加以限制，那么第三层的第二个和第四个灰色节点所产生的序列或total的值，都是一模一样的，因为我们可以用[3,4,x,x,...x]和[4,3,x,x,...x]来表示这两个灰色节点下的所有序列。所以，对于父函数选择某个choice，递归到当前函数时（根节点，选择4，递归到第二层的第二个节点），当前节点不能选择比这个choice的值小的choice2（不能选择3），因为父函数在选择choice2，并递归下去时，那个递归函数（第二层的第一个节点）已经选择了这个choice。

[480284856]

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

[mochacokie]

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

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。