力扣90题：子集II的 Java 实现

引言

LeetCode 是一个流行的在线编程平台，提供了大量的算法题目供开发者练习。第90题“子集II”是一个中等难度的题目，要求找出数组的所有子集，但是含重复数字的子集只计算一次。本文将介绍如何使用 Java 解决这个问题。

题目描述

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

注意：

• 本题中，元素的顺序很重要。例如 [1,2] 和 [2,1] 被认为是两个不同的子集。
• 该题相对于 78 题，解法一不需要回溯，解法二需要回溯。

示例:

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

问题分析

这个问题可以通过位操作或者回溯算法来解决。位操作的方法是将每个数字是否被选取作为一个二进制位来考虑，然后枚举所有可能的组合。回溯算法则是通过递归的方式，逐个决定每个数字是否被选取。

Java 实现

解法一：位操作

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums); // 对数组进行排序
    int n = nums.length;
    for (int i = 0; i < 1 << n; i++) {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                subset.add(nums[j]);
            }
        }
        res.add(new ArrayList<>(subset));
    }
    return res;
}

解法二：回溯算法

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums); // 对数组进行排序
    backtrack(res, new ArrayList<>(), nums, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> tempList, int[] nums, int start) {
    res.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复的数字
        tempList.add(nums[i]);
        backtrack(res, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

代码解释

1. 排序：无论是位操作还是回溯算法，首先需要对数组进行排序，以确保相同的数字相邻。
2. 位操作：通过遍历从 0 到 2^n - 1 的所有二进制数，每个二进制位代表数组中一个数字是否被选取。
3. 回溯算法：使用递归的方式，逐个决定每个数字是否被选取。为了避免重复的子集，当当前数字与前一个数字相同时，跳过当前数字。

结语

通过本文的介绍，你应该已经了解了如何使用 Java 解决 LeetCode 第90题“子集II”。这个问题考查了位操作和回溯算法的应用。希望本文能够帮助你更好地理解和掌握这些算法。如果你有任何问题或需要进一步的帮助，请随时在评论区提问。

。