组合总和
Combination Sum
本机进度仅保存在当前浏览器
题目描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。同一个数字可以无限制重复被选取。
示例：candidates = [2, 3, 6, 7]，target = 7，输出 [[2, 2, 3], [7]]。
解题思路
- 与组合模板的差异在递归出口与重复选取：和恰好等于 target 时收集；超过时剪枝返回。
- 允许重复选同一个数：递归时传 i 而不是 i + 1（当前层仍可再选自己）。
- 不重复的组合靠"只向后选"保证；candidates 先排序后可在和超过 target 时整层 break，剪枝更彻底。
参考实现
查看参考实现Python · 建议先自行作答
def combinationSum(candidates, target):
candidates.sort()
res, path = [], []
def backtrack(start, rest):
if rest == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
x = candidates[i]
if x > rest:
break # 后面更大，整层剪枝
path.append(x)
backtrack(i, rest - x) # i 不 +1，允许重复选
path.pop()
backtrack(0, target)
return res