含重复元素的子集问题中HashSet去重失效原因探究

给定一个可能包含重复元素的数组，返回其所有可能的子集（幂集），解集不能包含重复子集，返回顺序不限。

我尝试了两种看似类似的回溯解法：排序后通过相邻元素比较去重的代码可正常运行；但使用HashSet去重的代码在测试用例[10, 10, 1, 2, 2, 2, 10]中失效。两种代码如下：

可行代码 #

import java.util.*; 

public class test {
    static ArrayList<ArrayList<Integer>> subsets_with_duplicate(ArrayList<Integer> numbers) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Collections.sort(numbers);
        helper(res, new ArrayList<>(), numbers, 0);
        return res;
    }

    static void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> slate, ArrayList<Integer> numbers, int pos){
        int n=numbers.size();

        res.add(new ArrayList<Integer>(slate));
        //Set<Integer> set=new HashSet<>();
        for(int i=pos; i<n; i++){
            //if(!set.add(numbers.get(i)))
            if(i!=pos&&numbers.get(i).equals(numbers.get(i-1)))
                continue;
            slate.add(numbers.get(i));
            helper(res, slate, numbers, i+1);
            slate.remove(slate.size()-1);
        }
    }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(10, 10, 1, 2, 2, 2, 10));
        for(var v:subsets_with_duplicate(arr)){
            System.out.println(v);
        }
    }
}

失效代码 #

import java.util.*; 

public class test {
    static ArrayList<ArrayList<Integer>> subsets_with_duplicate(ArrayList<Integer> numbers) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        //Collections.sort(numbers);
        helper(res, new ArrayList<>(), numbers, 0);
        return res;
    }

    static void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> slate, ArrayList<Integer> numbers, int pos){
        int n=numbers.size();

        res.add(new ArrayList<Integer>(slate));
        Set<Integer> set=new HashSet<>();
        for(int i=pos; i<n; i++){
            if(!set.add(numbers.get(i)))
            //if(i!=pos&&numbers.get(i).equals(numbers.get(i-1)))
                continue;
            slate.add(numbers.get(i));
            helper(res, slate, numbers, i+1);
            slate.remove(slate.size()-1);
        }
    }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(10, 10, 1, 2, 2, 2, 10));
        for(var v:subsets_with_duplicate(arr)){
            System.out.println(v);
        }
    }
}

失效原因分析 #

核心问题在于HashSet去重逻辑无法适配未排序数组的重复元素分布，会导致重复子集生成，具体差异如下：

1. 可行代码的逻辑本质
   先对数组排序，让相同元素连续排列。然后通过i != pos && numbers.get(i).equals(numbers.get(i-1))判断，确保在当前递归层级的循环中，只有第一个出现的重复元素会被处理，后续相同元素直接跳过。这种方式从根源上避免了同一层级中选择不同位置的相同元素，彻底杜绝了重复子集的生成。

2. 失效代码的逻辑漏洞
   未排序的数组中，相同元素分散在不同位置：

   • HashSet仅在当前递归层级的循环中记录已处理的元素值，只能过滤当前循环内重复出现的元素，但无法阻止不同递归路径中选择不同位置的相同元素生成重复子集。例如，选择索引0的10+索引2的1，与选择索引6的10+索引2的1，会生成完全相同的[10,1]子集，而HashSet无法识别这种跨位置的重复选择。
   • 对于连续的重复元素（如原数组中的三个2），虽然当前层级的HashSet会过滤循环内的重复，但如果这些重复元素处于不同的递归起始位置（如pos=3、pos=4、pos=5），每个层级的HashSet都是新建的，会独立处理相同元素，导致生成多个完全相同的子集（如多次生成[2]）。

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