常用算法之回溯法

思路：在包含问题的解空间中，按照深度优先搜索的策略，从根节点出发深度探索解空间树，当探索到某一节点时，先判断该节点是否包含问题的解，如果包含，就从该节点触发继续探索下去，如果不包含该节点的解，则逐层向其祖先节点回溯。

示例

组合总和:给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。

假设输入数据为 candidates = [2,3,5], target = 8 。可以做如下初步分析：

1. 可以无限制重复被选取，比如4个2满足条件
2. 要找到所有的组合，也就是说要穷尽的去探索所有可能的情况
3. 当数据本身大于8或者和已经超过8则没有必要对接下来的数据做继续探索了

参照回溯法的思路：按照深度优先的规则，这里对“深度”的定义则是从第一元素开始，因为它可以被无限制的选取，那么就可以一直累加知道它会超过目标值，然后进行回溯

去掉了超过目标值的节点

• 优先选取第一个元素进行重复获取，这里就是一直往深度探索

• 条件满足后，开始执行回溯

• 可以计算得到它不满足和为8这个条件，继续回溯

• 当前分支的和仍然小于8，可以继续往下探索

• 条件不满足，进行回溯

• 仍然不满足和为8的条件，继续回溯

• 和小于8可以继续沿着这个分支进行深度探索，发现一个满足条件的解

• 仅接着开始下一次的分支尝试，仍不满足，这时就可以往相邻节点回溯

到新的头节点之后，继续遵循深度优先的原则即可

代码实现

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;
    }
复制代码