Java中如何避免List<List<Integer>>重复列表？求更优方案

嘿，这个问题我之前做组合求和类题目时也碰到过！你现在用排序+HashSet的方法确实能实现去重，但不仅代码繁琐，还会因为生成大量重复组合再事后过滤而浪费时间和空间。其实我们可以在回溯搜索的过程中直接避免生成重复组合，从根源上解决问题，效率会高很多。

核心思路 #

• 先对候选集合排序：排序后我们能方便地识别并跳过重复元素，同时还能提前终止不可能的递归分支（比如当前元素比剩余目标值大时，后面的元素肯定更大，直接break）。
• 回溯时控制起始索引+跳过重复元素：在每一层递归的循环中，我们从start索引开始遍历，并且如果当前元素和前一个元素相同，且不是当前层的第一个元素，就跳过它——这样就能避免同一层中重复选择相同元素，自然不会生成顺序不同但元素相同的组合（比如[2,2,3]和[2,3,2]这种情况根本不会出现）。

具体代码实现 #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        // 第一步：对候选数组排序，为剪枝做准备
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remainingTarget, int start, List<Integer> currentCombination, List<List<Integer>> result) {
        // 找到符合条件的组合，加入结果集
        if (remainingTarget == 0) {
            result.add(new ArrayList<>(currentCombination));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            int currentNum = candidates[i];
            // 因为数组已排序，当前元素比剩余目标大，后面的元素肯定更大，直接终止循环
            if (currentNum > remainingTarget) {
                break;
            }
            // 跳过同一层的重复元素，避免生成重复组合
            if (i > start && currentNum == candidates[i-1]) {
                continue;
            }

            // 选择当前元素
            currentCombination.add(currentNum);
            // 递归搜索：这里start传i，因为允许重复选择同一个元素（比如例子中的2可以选两次）
            backtrack(candidates, remainingTarget - currentNum, i, currentCombination, result);
            // 回溯，撤销选择
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum solution = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        System.out.println(solution.combinationSum(candidates, target));
        // 输出：[[2, 2, 3], [7]]
    }
}

为什么这个方案更优？ #

• 空间效率更高：不需要额外的HashSet存储中间结果，节省了内存开销。
• 时间效率更高：回溯过程中直接剪枝，避免生成大量无效的重复组合（比如[2,3,2]这种不符合要求的组合根本不会被生成），减少了不必要的递归调用和后续处理。
• 代码更简洁清晰：逻辑集中在回溯过程中，不需要事后对每个组合排序、去重，可读性更强。

对比你原来的方法：原来的思路是先生成所有可能的组合，再对每个组合排序后放入HashSet去重，相当于做了很多“无用功”——生成了大量不符合要求的组合，然后再丢弃。而提前剪枝的方法从根源上避免了这些无效操作。

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