1
class Solution {
2
  public List<List<Integer>> subsetsWithDup(int[] nums) {
3
    // Sort the input array to handle duplicates properly
4
    Arrays.sort(nums);
5
    // Start the recursion with an empty prefix list
6
    return subset(new ArrayList<Integer>(), nums);
7
  }
8

9
  // Recursive function to generate subsets
10
  public List<List<Integer>> subset(ArrayList<Integer> prefix, int[] nums) {
11
    List<List<Integer>> result = new ArrayList<>();
12

13
    // Base case: If there are no elements in nums, add the current prefix to result
14
    if (nums.length == 0) {
15
      result.add(new ArrayList<>(prefix));
16
      return result;
17
    }
18

19
    // Include the first element of nums in the prefix
20
    ArrayList<Integer> withCurrent = new ArrayList<>(prefix);
21
    withCurrent.add(nums[0]);
22

23
    // Recursive call with the first element included
24
    List<List<Integer>> left = subset(withCurrent, Arrays.copyOfRange(nums, 1, nums.length));
25

26
    List<List<Integer>> right = new ArrayList<>();
27

28
    // Check for duplicates in the prefix and decide whether to include the first element again
29
    if (prefix.size() > 0 && prefix.get(prefix.size() - 1) == nums[0]) {
30
      // If the current element is a duplicate, don't include it in the prefix
31
      // This avoids generating duplicate subsets
32
    } else {
33
      // If the current element is not a duplicate, include it in the prefix
34
      right = subset(prefix, Arrays.copyOfRange(nums, 1, nums.length));
35
    }
36

37
    // Combine the subsets with and without the current element
38
    left.addAll(right);
39
    return left;
40
  }
41
}