常用算法之回溯法

 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;
    }