组合求和问题两段代码差异：为何Code1仅返回唯一解？

当测试用例为候选数组[2,3,6,7]、目标值为7时，Code2返回包含排列重复的解：[[2,2,3],[2,3,2],[3,2,2],[7]]，而参考Code1仅返回无重复的唯一解：[[2,2,3],[7]]。以下是两段代码的核心差异，以及Code1无需借助Set即可去重的原理。

核心差异 #

• 回溯起始索引的控制逻辑不同：
  Code1的回溯函数接收start参数，每一层递归的循环从start位置开始遍历，并且递归调用时将当前的i作为下一轮的start，限制后续只能选择当前元素及之后的候选元素。
  Code2的递归函数循环始终从i=0开始，每一层都可以选择所有候选元素，导致不同顺序的排列被视为独立解加入结果集合。

Code1无需Set去重的原理 #

Code1通过从根源限制搜索路径的范围实现无重复组合：

1. 首先对候选数组排序（排序在这里主要为后续可能的剪枝优化做准备，核心是起始索引的控制）。
2. 回溯过程中，每一轮循环仅从start位置开始选择元素，选择当前元素后，下一轮递归的start设为当前的i。这意味着一旦选择了某个位置的元素，后续递归不会回头选择该元素之前的元素，从根本上避免了[2,3,2]这类不同顺序的重复组合产生。
3. 这种方式直接在搜索过程中过滤掉了重复的排列可能，不需要额外使用Set进行去重，既节省了空间，也提升了搜索效率。

Code1 实现 #

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(candidates);
      backtrack(list, new ArrayList<>(), candidates, target, 0);
      return list;  
    }
    public void backtrack(List<List<Integer>> list, List<Integer> temp, int[] nums, int remain, int start) {
        if(remain < 0) return;
        else if (remain == 0) list.add(new ArrayList<>(temp));
        else {
            for(int i = start; i < nums.length; i ++) {
                temp.add(nums[i]);
                backtrack(list, temp, nums, remain - nums[i], i);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

Code2 实现 #

class Solution {
    public static void combi(int n, int[] arr, int tar, List<List<Integer>> res, List<Integer> opt, int sum){
        if(sum>tar){
            return;
        }else if(sum == tar){
            res.add(new ArrayList<>(opt));
          
        }else{
        for(int i=0;i<n;i++){
             opt.add(arr[i]);
             combi(n, arr, tar, res, opt, sum+arr[i]);
             opt.remove(opt.size()-1);
             
        }}
    }
    public List<List<Integer>> combinationSum(int[] arr, int tar) {
       List<List<Integer>> res = new ArrayList<>();
       Arrays.sort(arr);
       combi(arr.length, arr, tar, res, new ArrayList<>(), 0);
       return res; 
    }
}

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