回溯组合问题疑问：index+1与i+1为何结果不同？

问题场景 #

这段Java代码用于求解从1到n中选取k个元素的组合问题，但运行结果不符合预期，修改递归参数后结果正确，下面分析两种参数写法的核心差异。

原错误代码 #

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
         List<Integer> list = new ArrayList<>();
         helper(k, n, list, 1);
         return res;
    }
    private void helper(int k, int n, List<Integer> list, int index){
        if(list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=index; i<=n; i++){
            list.add(i);
            helper(k, n, list, index+1); // 错误的参数传递
            list.remove(list.size()-1);
        }
        return;
    }
}

错误输出 #

当n=4，k=2时，输出结果包含重复或逆序的组合：

[[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,2],[3,3],[3,4],[4,2],[4,3],[4,4]]

修改后的正确代码 #

仅修改递归调用的参数，将index+1改为i+1：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
         List<Integer> list = new ArrayList<>();
         helper(k, n, list, 1);
         return res;
    }
    private void helper(int k, int n, List<Integer> list, int index){
        if(list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=index; i<=n; i++){
            list.add(i);
            helper(k, n, list, i+1); // 正确的参数传递
            list.remove(list.size()-1);
        }
        return;
    }
}

正确输出 #

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

两种参数写法的核心差异 #

• index+1的问题：index是当前递归层的起始参数，在整个for循环中它的值是固定的。比如第一层递归index=1，整个循环过程中index始终为1，所以*index+1*一直是2。这就导致每次递归进入下一层时，起始选择位置都是2，允许选择和当前层已选元素相同或更小的数（比如第一层选2后，下一层还能选2，出现[2,2]；第一层选3后，下一层能选2，出现[3,2]），完全违背了组合“不重复、元素递增”的要求。

• i+1的作用：i是for循环的迭代变量，每次循环都会递增。传递*i+1*给下一层递归，意味着下一层只能从当前选中元素的下一个位置开始选择。比如第一层选1后，下一层从2开始；第一层选2后，下一层从3开始，以此类推。这样就能保证组合中的元素严格递增，既不会出现重复元素，也不会出现逆序的情况，完全符合组合的定义。

内容的提问来源于stack exchange，提问作者user27919292