LeetCode 39.组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
思路
思路：经典回溯问题，同时做剪枝
上面这张图就能够看明白了：
- 对数组做排序（便于后面剪枝）
- 从
candidates数组中取数，每取一个数，后面仍有candidates.length种取法，因为可以重复取。取数的过程中，做剪枝：if (sum+candidates[i]>target) break，如果加上当前候选和超出target则直接break，不需要再做后面的加法（再次印证了为什么要做排序） - 如果没有超出
target，则将candidates[i]加入到path中，并进行下一层的递归，递归结束后移除加入到path中的candidates[i]元素 - 值得注意的是，递归时
backTracking(res, path, candidates, target, sum + candidates[i], i);，最后一位起始索引为i，说明第i位是可以被无限制重复选取的（只要每次加上不超过target就可以无限选）
代码
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {// 组合，回溯，剪枝List<List<Integer>> result = new ArrayList<>();Arrays.sort(candidates);backTracking(result, new ArrayList<>(), candidates, target, 0, 0);return result;}public void backTracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {// res -> 结果集// path -> 当前路径// candidates -> 候选数字// target -> 目标和// sum -> 当前和// idx -> 允许选取的下标起始位置if (sum == target) { // 说明找到了结果res.add(new ArrayList<>(path));return;}for (int i = idx; i < candidates.length; i++) {if (sum + candidates[i] > target) break;path.add(candidates[i]);backTracking(res, path, candidates, target, sum + candidates[i], i);path.remove(path.size() - 1); // 回溯，移除path的最后一个元素}}
}
