回溯算法09-子集II(Java/子集问题的去重方法)

9.子集II

题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

题目分析：

你想要编写一个函数，输入一个整数数组，输出该数组的所有子集，包括空集和本身。但是，如果数组中存在重复的元素，你不想得到重复的子集。

思路解析：

1. **排序数组**：首先，对输入的数组进行排序。这一步是为了确保相同的元素都相邻，方便后续的去重操作。
2. **回溯算法**：使用回溯算法来生成所有可能的子集。回溯算法是一种深度优先搜索的算法，通过不断地探索和回退来找到所有解。
3. **遍历数组**：在回溯的过程中，我们需要遍历数组中的每一个元素，并决定是否将其加入当前正在构建的子集。
4. **避免重复**：为了避免重复的子集，我们在遍历数组时，对于相同的元素，只选择第一个出现的，而跳过其余相同的元素。这样可以确保同一层级的递归中不会重复选择相同的元素。
5. **递归调用**：在每一轮递归中，我们将当前元素加入到路径中，然后递归调用函数，继续向下探索。当递归结束后，我们需要将当前元素从路径中移除，以便尝试其他可能的子集组合。
6. **保存结果**：在每一轮回溯中，当得到一个新的子集时，我们将其加入到结果集中。

Java代码实现

LinkedList<Integer> path = new LinkedList<>(); // 用于存储当前路径的集合
List<List<Integer>> result = new ArrayList<>(); // 用于存储最终结果的列表

/**
 * 找出给定整数数组中所有可能的子集，包含重复元素
 * @param nums 给定的整数数组
 * @return 所有可能的子集列表
 */
public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums); // 对数组进行排序，使相同元素相邻
    backtrack(nums, 0); // 调用回溯函数开始搜索
    return result; // 返回最终结果
}

/**
 * 回溯函数，用于搜索所有可能的子集
 * @param nums 给定的整数数组
 * @param startIndex 当前搜索的起始位置
 */
private void backtrack(int[] nums, int startIndex) {
    result.add(new ArrayList<>(path)); // 将当前路径加入最终结果，生成一个子集

    for (int i = startIndex; i < nums.length; i++) {
        if (i > startIndex && nums[i] == nums[i - 1]) {
            continue; // 如果当前元素和前一个元素相同，并且不是起始位置的元素，则跳过，避免生成重复子集
        }

        path.add(nums[i]); // 将当前元素加入路径
        backtrack(nums, i + 1); // 递归调用下一层搜索，更新起始位置为 i+1
        path.removeLast(); // 移除当前元素，尝试其他可能的组合
    }
}