Leetcode 90.子集II

力扣传送门(opens new window)

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

说明：解集不能包含重复的子集。

示例:

• 输入: [1,2,2]
• 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

解题思路：

当数组中存在重复元素时，我们需要在生成子集的过程中避免生成重复的子集。为了实现这一点，我们可以使用以下的解题思路：

1. 首先，对数组进行排序，这样相同的元素会相邻排列。
2. 创建一个结果列表 res来存储所有可能的子集。
3. 调用回溯函数 backTracking来生成子集，传入排序后的数组和初始索引0。
4. 在 backTracking函数中，首先将当前的子集加入到结果列表 res中。
5. 然后，从当前索引开始进行遍历，对于当前的元素，如果它与前一个元素相同且前一个元素没有被选择（即在当前子集中），则跳过该元素，避免生成重复的子集。
6. 如果当前元素与前一个元素不同或前一个元素已被选择，我们将当前元素加入到子集中，并递归调用 backTracking函数处理下一个元素。
7. 在递归调用返回后，我们将刚刚加入的元素从子集中弹出，以便在下一次循环中构建不同的子集。
8. 最后，当所有的元素都被遍历过后，回溯过程结束，我们就得到了所有可能的子集。
9. 返回结果列表 res作为函数的返回值。

代码实现：

class Solution {
    // 创建一个结果列表来存储所有可能的子集
    List<List<Integer>> res = new ArrayList<>();  

    public List<List<Integer>> subsetsWithDup(int[] nums) {  
        if (nums == null || nums.length == 0) {  
            return res;
        }
        // 对数组进行排序，使重复元素相邻排列
        Arrays.sort(nums);  
        // 调用回溯函数生成所有不包含重复子集的幂集
        backTracking(nums, 0, new ArrayList<>());  
        return res;  
    }

    private void backTracking(int[] nums, int index, List<Integer> subset) {  
        // 将当前的子集加入结果列表
        res.add(new ArrayList<>(subset)); 
        // 遍历数组中的元素
        for (int i = index; i < nums.length; i++) {  
            // 如果当前元素与前一个元素相同且前一个元素没有被选择，则跳过该元素，避免生成重复的子集
            if (i > index && nums[i] == nums[i - 1]) {  
                continue;
            }
            // 将当前元素加入子集
            subset.add(nums[i]); 
            // 递归调用回溯函数处理下一个元素
            backTracking(nums, i + 1, subset);  
            // 回溯，将刚加入的元素弹出，以便构建不同的子集
            subset.remove(subset.size() - 1);  
        }
    }
}