组合总和
Combination Sum
从候选数组中选出和等于 target 的组合，同一个数可以重复使用；不能有重复组合。
在力扣中练习题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
解题思路
主解法
回溯 · 排序 + 剪枝
从 start 往后选，允许重复选当前数，超过剩余就停
组合不关心顺序，[2,5] 和 [5,2] 是同一个组合。用 start 保证下一层只从当前下标往后选，就不会产生顺序不同的重复。
同一个数可以重复使用，所以递归时传 i 而不是 i+1；只有换下一个数时才让下标前进。
分步图解
候选已排序；同一元素可以重复选，所以递归仍从 i 开始，而不是 i+1。
先排序，循环中一旦 candidates[i] > remain 就 break：后面的候选只会更大，继续试没有意义。这个剪枝能省掉大量废枝。
分步图解
候选 6 大于剩余 5，后面只会更大，直接 break。
自拟候选 [2,5,6,9]、target 11 有三个解：2+2+2+5、2+9、5+6。注意 6 在剩余 1 时必须立即停止，而不是继续尝试 9。
时间 O(指数级，受剪枝影响)空间 O(target / minCandidate)
易错点
- 递归传 i+1：同一个数不能重复使用，会漏掉 2+2+2+5。
- 递归传 0：会产生 [2,5] 与 [5,2] 等重复组合。
- 不排序也不 break：结果正确但会多做大量无效递归。
- remain < 0 才停止：多走一层废枝，还可能把负数候选也带进来。
代码与演示
演示输入
candidates = [2,5,6,9]，target = 11候选已排序；同一元素可以重复选，所以递归仍从 i 开始，而不是 i+1。
查看 C++ 代码
延伸阅读
- “可以重复选”与“不能重复组合”并不矛盾：前者靠传 i，后者靠 start 只往后看。
- 如果候选含重复数字且每个只能用一次，需要先排序并在同一层跳过相同值。