1、题干
给你一个无重复元素的整数数组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 <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
2、解题
求所有组合的问题通常可以使用回溯算法就行求解。
回溯的基本实现步骤：
找到固定不变的量，每趟递归动态变化的量，结果集。
递归一定要有终止条件，终止条件要校验和添加结本趟结果到结果集合中。
循环递归，注意要先添加元素向前递归，之后进行回退操作；怎么添加的元素进行向后递归，就要怎么删除元素向前回溯。
方法一：（回溯法–结果校验处理）
利用回溯法的解答模版，可以获取所有可用排列的结果，但是可能造成重复问题。如：（2，2，3）和（2，3，2）实际上是想通过的结果。
所以保存结果时，需要校验是否重复，重复数据不能再次添加到结果集。
代码示例：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test50 {
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
// 不变的结果集
List<List<Integer>> result = new ArrayList<>();
// 每趟变量可变的元素
// 每趟添加的元素
List<Integer> tempList = new ArrayList<>();
// 添加元素的下标
int index = 0;
// 当前趟的结果和
int sum = 0;
// 递归（不变的：目标数组candidates，目标值target； 每趟变化的：临时数组tempList，添加元素下标index，每一趟当前和sum； 结果集）
goAndBack(candidates, target, tempList, index, sum, result);
return result;
}
private static void goAndBack(int[] candidates, int target, List<Integer> tempList, int index, int sum, List<List<Integer>> result) {
if (sum >= target) {
// 大于等于目标值时，可以结束当前趟遍历
if (sum == target) {
// 当前趟元素排序后校验结果集是否存在，不存在可以添加到结果集
ArrayList<Integer> oneGoal = new ArrayList<>(tempList);
Collections.sort(oneGoal);
if (!result.contains(oneGoal)){
result.add(oneGoal);
}
}
// 结果本趟递归，向前回溯
return;
}
for (int i = 0; i < candidates.length; i++) { // 因为元素可以重复添加，所以这里每次都从0号位置开始添加
// 添加元素，计算和，向后递归
tempList.add(candidates[i]);
sum = sum + candidates[i];
goAndBack(candidates, target, tempList, index + 1, sum + candidates[i], result);
// 删除添加的元素，减去当前值，向前回溯
sum = sum - candidates[i];
tempList.remove(index); // 或tempList.remove(tempList.size()-1);
}
}
public static void main(String[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
System.out.println(combinationSum(candidates, target));
}
}
方法二：（回溯法–指定遍历的起始位置）
上面的方法一中，每次都是从位置0开始遍历添加元素，直到符合条件为止，相对而言，递归和回溯的次数都比较多。
可以换一种方式，在向后递归的时候，指定起始遍历的位置，即：下一次对的起始位置也是本次递归的起始位置，不是从0开始。这样就在遍历组装结果的过程中避免了重复的可能，减少遍历和比较的次数，效率更高。
代码示例：
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
dfs(ans, temp, 0, 0, candidates, target);
return ans;
}
public void dfs(List<List<Integer>> ans, List<Integer> temp, int index, int sum, int[] candidates, int target) {
if (sum >= target) {
if (sum == target) {
ans.add(new ArrayList<>(temp));
}
return;
}
for (int i = index; i < candidates.length; i++) {
// 添加元素，向后递归
temp.add(candidates[i]);
dfs(ans, temp, i, sum + candidates[i], candidates, target); // 下一次遍历的位置i，最小也是index，避免过度回溯
// 删除元素，向前回溯
temp.remove(temp.size() - 1);
}
}
向阳前行，Dare To Be！！！