day27 代码随想录算法训练营 40. 组合总和 II

题目：40. 组合总和 II

我的感悟：

• 只要在路上就不怕走的慢。
• 卡尔的视频慢慢听 0.75倍听还是可以的。
• 只要状态好，就可以学。
• 多学会鼓励

理解难点：

代码难点：

• ① not used[i-1]等同于used[i-1]==0 
• 这里用的是True和False，所以用的是not used[i-1]
• ② i > 0 为了防止i-1越界
• ③ 剪枝为了每次计算剪枝，防止超时。

整理后我改的代码的示例：

class Solution:


    def backtracking(self, candidates, target, total, startIndex, used, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            # 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字
            if i > 0 and candidates[i] == candidates[i - 1] and not used[i - 1] :    # not used[i-1]等同于used[i-1]==0
                continue           

            total += candidates[i]
            if total > target:  # 剪枝操作
                break
            path.append(candidates[i])
            used[i] = True
            self.backtracking(candidates, target, total, i + 1, used, path, result)
            used[i] = False
            total -= candidates[i]
            path.pop()

    def combinationSum2(self, candidates, target):
        used = [False] * len(candidates)
        result = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, used, [], result)
        return result

通过截图：

扩展写法：

资料：