☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Subsets II

Medium TUF ID 868 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of integers that may contain duplicates. Return every possible subset (the power set) without duplicate subsets. Two subsets are the same if they contain the same values with the same multiplicities; [1, 2] taken from indices 0, 1 and from indices 0, 2 of [1, 2, 2] is one subset. The subsets may be returned in any order, and the elements inside a subset may be in any order.

Constraints: 1 ≤ n ≤ 10, -10 ≤ nums[i] ≤ 10.

Example 1

nums = [1, 2, 2]
answer = [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]
// the plain power set would have 8 entries; [2] and [1, 2] each appear twice there

Example 2

nums = [0]
answer = [[], [0]]

Example 3

nums = [3, 3, 3]
answer = [[], [3], [3, 3], [3, 3, 3]]     // n + 1 subsets, not 2^n

Approach 1: Brute force, generate everything and de-duplicate with a set

Intuition. Generate all 2^n subsets of the sorted array by bitmask and insert each into a set. Sorting first means two index subsets with the same values produce identical lists (elements are always appended in index order, hence in sorted order), so the set recognises them as equal. It works, but the duplicate subsets are built and hashed before being discarded, and when the array has many equal values nearly all of the 2^n work is wasted: [3, 3, 3] builds eight lists to keep four.

Algorithm.

  1. Sort a copy of nums.
  2. For every mask from 0 to 2^n - 1, build the list of elements whose bit is set and insert it into a LinkedHashSet.
  3. Return the set as a list.
static List<List<Integer>> bruteForce(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    Set<List<Integer>> seen = new LinkedHashSet<>();
    int n = a.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) subset.add(a[i]);
        }
        seen.add(subset);
    }
    return new ArrayList<>(seen);
}

Complexity. Time O(2^n · n): every subset is built and hashed in O(n). Space O(2^n · n) for the set in the worst case (all distinct values).

Approach 2: Optimal, sorted loop that skips equal values at the same level

Intuition. Think of building a subset by repeatedly choosing the next element to append, always from positions after the last one chosen. Every node of this recursion tree, including the root with the empty list, is a distinct subset, so we record cur on entry rather than only at the leaves. Duplicates arise when, at one level, we try to append a value equal to one we already tried at that same level: whatever follows is drawn from the same sorted remainder, so the results repeat. Sorting makes equal values adjacent and the test j > start && a[j] == a[j - 1] catches exactly that case. The j > start part is essential: a[j - 1] is a duplicate sibling only if it belongs to this level; if it is the element the parent chose, appending another copy of it is legitimate (that is how [2, 2] is produced).

Algorithm.

  1. Sort a copy of nums.
  2. loopRec(start, cur): record a copy of cur.
  3. For j = start .. n - 1: if j > start and a[j] == a[j - 1], skip.
  4. Append a[j], recurse with start = j + 1, remove it.
static List<List<Integer>> optimal(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    List<List<Integer>> out = new ArrayList<>();
    loopRec(a, 0, new ArrayList<>(), out);
    return out;
}

static void loopRec(int[] a, int start, List<Integer> cur, List<List<Integer>> out) {
    out.add(new ArrayList<>(cur));                     // the current prefix of choices is itself a subset
    for (int j = start; j < a.length; j++) {
        if (j > start && a[j] == a[j - 1]) continue;   // this value was already extended at this level
        cur.add(a[j]);
        loopRec(a, j + 1, cur, out);
        cur.remove(cur.size() - 1);
    }
}

Dry run on sorted a = [1, 2, 2]:

start cur on entry recorded loop
0 [] [] j = 0: take 1
1 [1] [1] j = 1: take 2
2 [1, 2] [1, 2] j = 2: take 2 (j == start, so allowed)
3 [1, 2, 2] [1, 2, 2] loop empty, return
2 [1, 2]   j = 2 done, return
1 [1]   j = 2: a[2] == a[1] and j > start: skip; return
0 []   j = 1: take 2
2 [2] [2] j = 2: take 2
3 [2, 2] [2, 2] return
0 []   j = 2: a[2] == a[1] and j > start: skip; done

Six subsets recorded, none repeated, no set required.

Complexity. Time O(2^n · n) in the worst case (all values distinct gives the full power set, each copied in O(n)); with duplicates the tree is exactly as large as the answer, which is the best possible. Sorting adds O(n log n). Space O(n) for the recursion and the working list, beyond the output.

Approach 3: Pick / not-pick where “not pick” skips the whole run of equal values

Intuition. The same uniqueness rule in two-branch form. Picking a[i] continues normally at i + 1. Not picking a[i] must also refuse every later copy of the same value: “skip this 2, take the next 2” is the same subset as “take this 2, skip the next”. So the not-pick branch jumps to the first index holding a different value. Subsets are recorded at the leaves, as in the plain power-set recursion.

Algorithm.

  1. Sort a copy of nums.
  2. skipRec(i, cur): if i == n, record cur and return.
  3. Pick: append a[i], recurse with i + 1, remove it.
  4. Not pick: advance next past every element equal to a[i], recurse with next.
static List<List<Integer>> pickNotPickSkip(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    List<List<Integer>> out = new ArrayList<>();
    skipRec(a, 0, new ArrayList<>(), out);
    return out;
}

static void skipRec(int[] a, int i, List<Integer> cur, List<List<Integer>> out) {
    if (i == a.length) {
        out.add(new ArrayList<>(cur));
        return;
    }
    cur.add(a[i]);                                     // pick a[i]
    skipRec(a, i + 1, cur, out);
    cur.remove(cur.size() - 1);
    int next = i + 1;                                  // not pick: skip every later element equal to a[i]
    while (next < a.length && a[next] == a[i]) next++;
    skipRec(a, next, cur, out);
}

Complexity. Same as Approach 2: O(2^n · n) worst case, output-sized in practice, O(n) extra space.

Approach 4: Iterative doubling with a “last round” pointer

Intuition. Without duplicates, the power set can be built iteratively: for each element, copy every existing subset and append the element. With duplicates, when a[i] equals a[i - 1], extending all existing subsets would repeat the ones already extended by the previous copy. The subsets that may safely be extended are exactly those created in the previous round, because they are the only ones that already end in a copy of this value. Remembering where the previous round started gives the rule for free.

Algorithm.

  1. Sort a copy; start with out = [[]] and prevStart = 0.
  2. For each i: let from = prevStart if a[i] == a[i - 1], otherwise 0; let size = out.size().
  3. For j = from .. size - 1, append a copy of out[j] extended by a[i].
  4. Set prevStart = size.
static List<List<Integer>> iterative(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    List<List<Integer>> out = new ArrayList<>();
    out.add(new ArrayList<>());
    int prevStart = 0;                                 // index of the first subset added in the previous round
    for (int i = 0; i < a.length; i++) {
        int from = (i > 0 && a[i] == a[i - 1]) ? prevStart : 0;
        int size = out.size();
        for (int j = from; j < size; j++) {
            List<Integer> extended = new ArrayList<>(out.get(j));
            extended.add(a[i]);
            out.add(extended);
        }
        prevStart = size;
    }
    return out;
}

On [1, 2, 2]: after 1 the list is [], [1] (prevStart = 1); after the first 2 it is [], [1], [2], [1, 2] (prevStart = 2); the second 2 extends only indices 2 and 3, adding [2, 2] and [1, 2, 2].

Complexity. Time O(2^n · n) worst case, output-sized with duplicates. Space O(1) beyond the output; no recursion.

Edge cases and pitfalls