Leetcode 39 组合总和

Source: Dev.to

（未提供需要翻译的正文内容。如需翻译，请粘贴或提供完整的文章文本。）

Problem Statement

给定一个由互不相同的整数构成的数组 candidates 和一个目标整数 target，返回 所有唯一的组合，使得所选数字的和等于 target。
每个候选数字可以被无限次使用。如果至少有一个数字的使用频率不同，则认为两个组合不同。

示例：[2,3,3]、[3,2,3] 和 [3,3,2] 表示相同的唯一组合。

示例

输入

candidates = [2,3,5]
target = 8

输出

[[2,2,2,2], [2,3,3], [3,5]]

数学表述

该问题可以表述为寻找非负整数 x, y, z，使得

2·x + 3·y + 5·z = 8

解决方案

class Solution:
    def combinationSum(self, candidates, target):
        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                # found a valid combination
                results.append(list(comb))   # make a shallow copy
                return
            if remain < 0:
                # exceeded the sum, stop exploring this path
                return

            for i in range(start, len(candidates)):
                # choose the candidate
                comb.append(candidates[i])
                # explore further with the same start index (allow reuse)
                backtrack(remain - candidates[i], comb, i)
                # backtrack
                comb.pop()

        backtrack(target, [], 0)
        return results

常见陷阱

深度优先搜索演练

下面展示了示例（candidates = [2,3,5]，target = 8）的递归树（每个节点显示 i – 索引，v – 值，remain，以及 start）。

root (target: 8)
└── [i:0, v:2] remain: 6, start: 0
    ├── [i:0, v:2] remain: 4, start: 0
    │   ├── [i:0, v:2] remain: 2, start: 0
    │   │   ├── [i:0, v:2] remain: 0, start: 0 ── Success → [2,2,2,2]
    │   │   ├── [i:1, v:3] remain: -1 ── Fail
    │   │   └── [i:2, v:5] remain: -3 ── Fail
    │   ├── [i:1, v:3] remain: 1, start: 1
    │   │   ├── [i:1, v:3] remain: -2 ── Fail
    │   │   └── [i:2, v:5] remain: -4 ── Fail
    │   └── [i:2, v:5] remain: -1 ── Fail
    ├── [i:1, v:3] remain: 3, start: 1
    │   ├── [i:1, v:3] remain: 0 ── Success → [2,3,3]
    │   └── [i:2, v:5] remain: -2 ── Fail
    └── [i:2, v:5] remain: 1, start: 2
        └── [i:2, v:5] remain: -4 ── Fail
└── [i:1, v:3] remain: 5, start: 1
    ├── [i:1, v:3] remain: 2, start: 1
    │   ├── [i:1, v:3] remain: -1 ── Fail
    │   └── [i:2, v:5] remain: -3 ── Fail
    └── [i:2, v:5] remain: 0 ── Success → [3,5]
└── [i:2, v:5] remain: 3, start: 2
    └── [i:2, v:5] remain: -2 ── Fail

参考表