下面的for循环辨别遍历他的9个子节点，留意这里的i是从start末尾的，所以有能够还没有9个子树，前面说过，假设从9个数字中选择一个之后，第2次就只能从剩下的8个选择了，第3次就只能从剩下的7个中选择了……

在第20行dsf中的start是i+1，这里要说一下为什么是i+1。比如我选择了3，下次就应该从4末尾选择，假设不加1，下次还从3末尾就出现了数字重复，清楚与题中的要求不符

for循环的i为什么不能每次都从1末尾，假设每次都从1末尾就会出现结果重复，比如选择了[1，2]，下次能够就会选择[2，1]。

假设对回溯算法不懂的，能够最不容易了解的就是最后一行，为什么要撤销选择。假设常常看我群众号的同窗能够知道，也就是我常常提到的分支污染成绩，由于list是援用传递，当从一个分支跳到另一个分支的时分，假设不把前一个分支的数据给移除掉，那么list就会把前一个分支的数据带到下一个分支去，形成结果错误(下面会讲)。那么除了把前一个分支的数据给移除以外还有一种方式就是每个分支都创立一个list，这样每个分支都是一个新的list，都不相互关扰，也就是下面图中这样

代码如下

public List<List<Integer>> combinationSum3(int k, int n) { 

    List<List<Integer>> res = new ArrayList<>(); 

    dfs(res, new ArrayList<>(), k, 1, n); 

    return res; 

}private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { 

    //终止条件，假设满足这个条件，再往下找也没什么意义了 

    if (list.size() == k || n <= 0) { 

        //假设找到一组适宜的就把他参加到集合list中 

        if (list.size() == k && n == 0) 

            res.add(new ArrayList<>(list)); 

        return; 

    } 

    //经过循环，辨别遍历9个子树 

    for (int i = start; i <= 9; i++) { 

        //创立一个新的list，和原来的list撇清关系，对以后list的修正并不会影响到之前的list 

        List<Integer> subList = new LinkedList<>(list); 

        subList.add(i); 

        //递归 

        dfs(res, subList, k, i + 1, n - i); 

        //留意这里没有撤销的操作，由于是在一个新的list中的修正，原来的list并没有修正， 

        //所以不需求撤销操作 

    } 

} 

我们看到最后并没有撤销的操作，这是由于每个分支都是一个新的list，你对以后分支的修正并不会影响到其他分支，所以并不需求撤销操作。

留意：大家尽量不要写这样的代码，这种方式虽然也能处置，但每个分支都会重新创立list，效率很差。

(责任编辑：admin)