Java含重复元素列表的幂集生成问题：输出不符合预期

你的代码无法正确处理含重复元素的列表，核心源于三个设计错误，导致无法生成包含重复元素的子集，且递归逻辑混乱：

• 当前子集用HashSet存储：HashSet自动忽略重复元素，添加第二个2时集合无变化，无法生成[2,2]这类子集。
• 重复元素处理逻辑冗余错误：递归末尾额外调用的分支属于多余逻辑，且跳过重复元素的位置错误，直接丢失了本该处理的元素分支。
• 结果集类型选择错误：Set<Set<T>>的内层Set无法保留重复元素，即使生成[2,2]，转成Set后也会变成[2]，不符合期望输出要求。

修复后的代码 #

import java.util.*;

public class PowerSetWithDuplicates {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 2);
        Set<List<Integer>> powerSet = generatePowerSet(list);
        // 转换为有序列表便于查看
        List<List<Integer>> sortedResult = new ArrayList<>(powerSet);
        sortedResult.sort((a, b) -> {
            if (a.size() != b.size()) {
                return a.size() - b.size();
            }
            return a.toString().compareTo(b.toString());
        });
        System.out.println(sortedResult);
    }

    public static <T extends Comparable<T>> Set<List<T>> generatePowerSet(List<T> list) {
        Set<List<T>> powerSet = new HashSet<>();
        // 先排序，确保重复元素相邻
        List<T> sortedList = new ArrayList<>(list);
        Collections.sort(sortedList);
        generatePowerSet(sortedList, 0, new ArrayList<>(), powerSet);
        return powerSet;
    }

    private static <T extends Comparable<T>> void generatePowerSet(List<T> sortedList, int index, List<T> currentList, Set<List<T>> powerSet) {
        // 存入当前子集的副本
        powerSet.add(new ArrayList<>(currentList));

        for (int i = index; i < sortedList.size(); i++) {
            // 跳过重复元素，避免生成重复子集
            if (i > index && sortedList.get(i).equals(sortedList.get(i - 1))) {
                continue;
            }
            // 包含当前元素
            currentList.add(sortedList.get(i));
            // 递归处理下一个元素
            generatePowerSet(sortedList, i + 1, currentList, powerSet);
            // 回溯移除当前元素
            currentList.remove(currentList.size() - 1);
        }
    }
}

代码逻辑说明 #

1. 排序输入列表：让重复元素相邻，方便后续跳过重复分支，避免生成重复子集。
2. 用List存储当前子集：允许保留重复元素，支持生成[2,2]这类包含重复元素的子集。
3. 优化递归逻辑：通过循环遍历元素，遇到重复元素时跳过；每次递归选择是否包含当前元素，回溯时移除元素，覆盖所有可能的子集组合。
4. 结果集用Set<List>：既保留含重复元素的子集，又能自动去重不同路径生成的相同子集。

运行输出 #

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

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