共计 1460 个字符，预计需要花费 4 分钟才能阅读完成。
39. 组合总和
题目起源：力扣（LeetCode）
https://leetcode-cn.com/problems/combination-sum
题目
给定一个无反复元素的数组 candidates 和一个指标数 target，找出 candidates 中所有能够使数字和为 target 的组合。
candidates 中的数字能够无限度反复被选取。
阐明：
- 所有数字（包含 target）都是正整数。
- 解集不能蕴含反复的组合。
示例 1：
输出：candidates = [2,3,6,7], target = 7,
所求解集为：[[7],
[2,2,3]
]示例 2：
输出：candidates = [2,3,5], target = 8,
所求解集为：[[2,2,2,2],
[2,3,3],
[3,5]
]提醒：
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- candidate 中的每个元素都是举世无双的。
- 1 <= target <= 500
解题思路
思路：回溯
先审题，题目给定无反复元素数组和目标值 target，要求找出数组中所有能够使数组元素和为 target 的组合。
其中数组中的元素都为正整数，能够重复使用数组中的元素，然而解集中不能存在反复的组合。
这里能够看示例 1：
输出：candidates = [2,3,6,7], target = 7,
所求解集为：[[7],
[2,2,3]
]这里答案并没有 [2,3,2] 或 [3,2,2]，因为这两者就被视为与 [2,2,3] 为反复的组合，这里须要特地留神。
这里这里通过画图来阐明，以下是简略图例：
在这里 $\color{red}{✖}$ 示意不抉择此元素，这样就能够防止元素组合反复的状况，$\color{green}{✖}$ 示意以后门路抉择元素和大于目标值 target，而 $\color{green}{✔}$ 则示意以后门路抉择元素和等于目标值，能够将此组合增加到返回列表中。
在下面的图例中，只是简略画出了一个分支的状况，然而其余分支抉择的策略雷同，这里就省略了。若有不太明确的中央，倡议能够自行在草稿上进行补全，也帮忙本人了解。
那么就依照下面图例中的思路，用代码进行实现，具体如下。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
# 后果列表
ans = []
# 可能的组合
tmp = []
def helper(idx, total):
""" 回溯，求组合总和
Args:
idx: 选取元素索引
total: 组合中的元素和
"""
# 基准条件
# 当元素和大于目标值，间接返回
if total > target:
return
# 当元素和等于目标值，将组合增加到后果中，返回
if total == target:
ans.append(tmp[::])
return
# 进入分支，同时防止反复组合
for i in range(idx, len(candidates)):
# 更新 total 值，total += candidates[i]
# 同时将以后元素尝试增加到组合中
tmp.append(candidates[i])
# 再次进入递归
# 这里能够看文章图例，递归向下，可选元素是从本身开始抉择
# 这里同时也能防止组合反复，因为不会再次抉择索引 i 后面对应的元素
helper(i, total)
# 回溯，回退组合元素及 total 值
tmp.pop()
total -= candidates[i]
total = 0
helper(0, total)
return ans欢送关注
公众号【书所集录】
正文完
