【题目描述】
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 ：
输入：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 <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素 互不相同
- 1 <= target <= 40
【题目链接】. - 力扣（LeetCode）
【解题代码】
package dp;
import java.util.*;
public class CombinationSum {
public static void main(String[] args) {
//int[] candidates = {2, 3, 6, 7};
int[] candidates = {1, 2, 3};
System.out.println("开始计算。。。");
long start = System.currentTimeMillis();
List<List<Integer>> numLists = new CombinationSum().combinationSum(candidates, 4);
System.out.println("运行时长：" + (System.currentTimeMillis() - start) + "ms");
for (List<Integer> numList : numLists) {
System.out.println(Arrays.toString(numList.toArray()));
}
}
private List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> numLists = new ArrayList<>();
List<Integer> numList = new ArrayList<>();
doCombinationSum(candidates, 0, target, numList, numLists);
return numLists;
}
private void doCombinationSum(int[] candidates, int n, int target, List<Integer> numList, List<List<Integer>> numLists) {
if (target == 0) {
numLists.add(new ArrayList<>(numList));
} else if (n < candidates.length) {
doCombinationSum(candidates, n + 1, target, numList, numLists);
if (target >= candidates[n]) {
numList.add(candidates[n]);
doCombinationSum(candidates, n, target - candidates[n], numList, numLists);
numList.remove(numList.size() - 1);
}
}
}
}
【解题思路】
看到此题描述，第一反应就是应该采用“回溯算法”：依次遍历数组candidates 里面数字，根据题意对当前索引i的数字做两种选择：
- 当前数字candidates[i]不加入候选队列：直接递归处理下一个索引数字i+1；
- 当前数字candidates[i]如果小于target，选择将其加入候选队列：将目标整数 target减去当前candidates[i]，因为数字可以重复选择，再次递归处理索引数字i；
- 目标整数 target为0,说明当前候选数字序列满足要求，添加到结果集，此趟递归结束
- 按照上述思路完成代码编写，提交LeetCode成功
【解题步骤】
- 定义一个回溯递归函数doCombinationSum，参数包括整数数组 candidates，当前索引值n,目标值target,当前候选数列numList，结果数列numLists：
private void doCombinationSum(int[] candidates, int n, int target, List<Integer> numList, List<List<Integer>> numLists) - 如果目标值target为0，说明当前候选数字序列numList满足要求，添加到结果集numLists
if (target == 0) { numLists.add(new ArrayList<>(numList)); } - 如果数组遍历还没遍历完，首先选择不选择当前数字，直接递归处理下一个索引数字即可
} else if (n < candidates.length) { doCombinationSum(candidates, n + 1, target, numList, numLists); - 接下来，如果当前数字小于等于目标值target，那么选择此数字，将此数字添加到候选数字序列，将目标值target去当前candidates[i]，并从当前索引重复递归，递归完毕，回溯将次数字从候选数字序列中删除
if (target >= candidates[n]) { numList.add(candidates[n]); doCombinationSum(candidates, n, target - candidates[n], numList, numLists); numList.remove(numList.size() - 1); }
【思考总结】
- 了解掌握回溯算法定义：回溯算法定义 回溯算法，是一种选优搜索法，又称为试探法，按选优条件向前搜索以达到目标。 回溯算法简要说：但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。 而满足回溯条件的某个状态的点称为“回溯点”。
- 回溯与递归的区别：递归的基本性质就是函数调用，在处理问题的时候，递归往往是把一个大规模的问题不断地变小然后进行推导的过程。 回溯则是利用递归的性质，从问题的起始点出发，不断地进行尝试，回头一步甚至多步再做选择，直到最终抵达终点的过程；
- LeetCode解题之前，一定不要看题解，看了就“破功”了！
