思路：在包含问题的解空间中，按照深度优先搜索的策略，从根节点出发深度探索解空间树，当探索到某一节点时，先判断该节点是否包含问题的解，如果包含，就从该节点触发继续探索下去，如果不包含该节点的解，则逐层向其祖先节点回溯。
示例
组合总和:给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。
假设输入数据为 candidates = [2,3,5], target = 8。可以做如下初步分析：
- 可以无限制重复被选取，比如4个2满足条件
- 要找到所有的组合，也就是说要穷尽的去探索所有可能的情况
- 当数据本身大于8或者和已经超过8则没有必要对接下来的数据做继续探索了
参照回溯法的思路：按照深度优先的规则，这里对“深度”的定义则是从第一元素开始，因为它可以被无限制的选取，那么就可以一直累加知道它会超过目标值，然后进行回溯
去掉了超过目标值的节点
- 优先选取第一个元素进行重复获取，这里就是一直往深度探索
- 条件满足后，开始执行回溯
- 可以计算得到它不满足和为8这个条件，继续回溯
- 当前分支的和仍然小于8，可以继续往下探索
- 条件不满足，进行回溯
- 仍然不满足和为8的条件，继续回溯
- 和小于8可以继续沿着这个分支进行深度探索，发现一个满足条件的解
- 仅接着开始下一次的分支尝试，仍不满足，这时就可以往相邻节点回溯
到新的头节点之后，继续遵循深度优先的原则即可
代码实现
代码语言：javascript复制 public List<List<Integer>> combinationSum(int[] candidates, int target) {
//先排序，方便直接抛弃大的值
Arrays.sort(candidates);
//开始深度搜索，从图中第一个位置开始找
List<List<Integer>> rs = dst(0,target,candidates);
return rs;
}
public List<List<Integer>> dst(int start,int target,int[] candidates){
List<List<Integer>> rs = new ArrayList<>();
for(int i=start;i<candidates.length;i ){
int v=candidates[i];
if(v>target){
break;//不满足条件，结束探索
}else if(v==target){
//刚好满足解的条件，加入解集
rs.add(Arrays.asList(v));
} else{
//深度优先探索
List<List<Integer>> sc= dst(i,target-v,candidates);
for(List<Integer> s:sc){
//组合后续的结果
List<Integer> f = new ArrayList<>();
f.add(v);
f.addAll(s);
rs.add(f);
}
}
}
return rs;
}
