自己解法
因为有每步减做拆解的感觉，就想到了深度优先遍历加回溯，这也是我理解最深的递归了吧哈哈，并且这种数组为了剪枝一般都是先排序，不过这个题我忽略了，只排了序，没去重，
后面补上了下标只能越去越大就好了。
class Solution {
List<List<Integer>> output = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<Integer> res = new ArrayList<>();
dfs(candidates, target, res, 0);
return output;
}
private void dfs(int[] candidates, int target, List<Integer> res, int j) {
if (target == 0) {
output.add(new ArrayList(res));
}
for (int i = j; i < candidates.length; i++) {
if (candidates[i] > target) {
break;
}
res.add(candidates[i]);
dfs(candidates, target - candidates[i], res, i);
res.remove(res.size() - 1);
}
}
}
官方解法
解法完全一样，就是他这个有点啰嗦，还有剪枝的时候可以直接break，以为后面越取越大了。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
int len = candidates.length;
// 排序是为了提前终止搜索
Arrays.sort(candidates);
dfs(candidates, len, target, 0, new ArrayDeque<>(), res);
return res;
}
/**
* @param candidates 数组输入
* @param len 输入数组的长度，冗余变量
* @param residue 剩余数值
* @param begin 本轮搜索的起点下标
* @param path 从根结点到任意结点的路径
* @param res 结果集变量
*/
private void dfs(int[] candidates,
int len,
int residue,
int begin,
Deque<Integer> path,
List<List<Integer>> res) {
if (residue == 0) {
// 由于 path 全局只使用一份，到叶子结点的时候需要做一个拷贝
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 在数组有序的前提下，剪枝
if (residue - candidates[i] < 0) {
break;
}
path.addLast(candidates[i]);
dfs(candidates, len, residue - candidates[i], i, path, res);
path.removeLast();
}
}
}
