https://leetcode-cn.com/problems/combination-sum/solution/hui-shuo-suan-fa-di-gui-java-by-longchenghuang/

总结：回溯主要是通过递归对所有情况进行遍历，通过剪枝降低复杂度。难点在于如何通过剪枝降低系统栈深度，降低时间复杂度？

后面选取的数不能比前面选的数还要小，即 “更深层的边上的数值不能比它上层的边上的数值小”，本题通过这种方式降低复杂度。

List<List<Integer>> set=new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    //排序
    Arrays.sort(candidates); 
    List<Integer> list=new ArrayList<Integer>();
    trace(0,list,candidates,target);
    return set;
}
public void trace(int index,List<Integer> list,int[] candidates,int tempTarget){
    if(tempTarget==0) {
        //引用类型，需要创建新的对象
        List<Integer> num=new ArrayList<Integer>(list);
        set.add(num);
        return;
    }
    if(index>=candidates.length||tempTarget<candidates[index]) return;
    //以index为起点，就是考虑了去重的问题，且考虑到了数字可以多次使用的条件
    //通过这种方式，迭代会一直从同一个下标开始，直到不符合条件，下标加一，
    //对比i从零开始的情况
    for(int i=index;i<candidates.length;i++){
        list.add(candidates[i]);
        trace(i,list,candidates,tempTarget-candidates[i]);
        //回溯的关键，进行同一层的下一步时，需要先删除这一层上一步的元素
        list.remove(list.size()-1);
    }
}

---