Subsets With Duplicates (Generate Unique Subsets When Elements Repeat)

• Subsets With Duplicates – generates every distinct subset when the input may contain repeated elements.
• Sort precondition – sorting places equal values next to each other, enabling the duplicate-skip rule.
• Iterative doubling – for each element, copy and extend existing subsets; for a duplicate, restrict this to subsets created in the previous round.
• Previous-round tracking – store the start index of the previous round so only those subsets get the new duplicate appended.
• Complexity – proportional to the number of distinct subsets produced, which is at most 2^n.

What is the Subsets With Duplicates problem?

Given a collection of numbers that may contain duplicates, return all possible unique subsets (the power set) without any two subsets being identical. For example, given [1, 2, 2], the output should be [[], [1], [2], [1,2], [2,2], [1,2,2]] and must not include [2] twice.

At the National Bank of India, Priya has a set of promotional discount coupons. Some coupons are identical. The marketing team needs every distinct combination of coupons she could apply, without counting the same combination twice just because two coupons are interchangeable.

Why is sorting required?

Sorting places equal elements next to each other. This adjacency is what lets us detect when the current element is a repeat of the previous one. Without sorting, two equal elements could be far apart, and the algorithm would not know to apply the duplicate-skip rule.

// Before sorting: [2, 1, 2] -> cannot detect adjacency
// After sorting:  [1, 2, 2] -> second 2 is adjacent to first 2
Arrays.sort(nums);

How does the iterative approach work?

Start with a result list containing only the empty subset. For each element, copy every eligible subset, append the current element to the copy, and add it to the result. The trick is defining "eligible."

• If the current element is different from the previous one, all existing subsets are eligible.
• If the current element equals the previous one, only the subsets created in the previous round are eligible.

package com.bank.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CouponBundleGenerator {
    public static List<List<Integer>> subsetsWithDup(int[] coupons) {
        Arrays.sort(coupons);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        int previousRoundStart = 0;

        for (int i = 0; i < coupons.length; i++) {
            int start = (i > 0 && coupons[i] == coupons[i - 1])
                    ? previousRoundStart
                    : 0;
            int size = result.size();
            for (int j = start; j < size; j++) {
                List<Integer> newSubset = new ArrayList<>(result.get(j));
                newSubset.add(coupons[i]);
                result.add(newSubset);
            }
            previousRoundStart = size;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] coupons = {5, 10, 5};
        List<List<Integer>> bundles = subsetsWithDup(coupons);
        System.out.println("Distinct coupon bundles: " + bundles);
    }
}

Distinct coupon bundles: [[], [5], [10], [5, 10], [5, 5], [5, 5, 10]]

Why does extending only the previous round prevent duplicates?

A duplicate element must attach only to subsets that already contain the earlier copy. If it extended all subsets, it would create a subset with one copy that is indistinguishable from one already produced with the first copy.

• For [1, 2, 2] after processing the first 2:
• Result so far: [[], [1], [2], [1,2]]
• Subsets from the previous round (indices 2-3): [2], [1,2]

When processing the second 2, we extend only [2] and [1,2] to get [2,2] and [1,2,2]. If we extended [] and [1] too, we would produce [2] and [1,2] again, which are duplicates.

How does the backtracking approach work?

The backtracking version uses a recursive choice tree with a skip condition: within the same recursion level, skip an element if it equals the previous one.

package com.bank.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CouponBundleBacktrack {
    public static List<List<Integer>> subsetsWithDup(int[] coupons) {
        Arrays.sort(coupons);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(coupons, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] coupons, int index,
                                  List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));
        for (int i = index; i < coupons.length; i++) {
            if (i > index && coupons[i] == coupons[i - 1]) {
                continue; // skip duplicate at same recursion level
            }
            current.add(coupons[i]);
            backtrack(coupons, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

What is the time and space complexity?

| Aspect | Complexity |
|---|---|
| Time | O(n * 2^n) in the worst case, where n is the array length |
| Space | O(2^n) for the result list |
| Sorting | O(n log n) preprocessing |

The work is proportional to the number of distinct subsets produced. When there are many duplicates, the actual number of subsets is much less than 2^n.

What are common mistakes?

// Wrong: forgetting to sort
// Without sorting, duplicates are not adjacent and the skip rule fails
int[] nums = {2, 1, 2};
// The algorithm sees 2, then 1 (different), then 2 (different from 1)
// and produces [2] twice

// Correct: always sort first
Arrays.sort(nums); // now [1, 2, 2]

Another mistake is updating previousRoundStart at the wrong time. It must be set to the size of the result before the current round's additions, not after.

What are the edge cases?

• Empty array: return [[]] (only the empty subset).
• All elements identical: for [5, 5, 5], the result is [[], [5], [5,5], [5,5,5]] with four subsets instead of eight.
• No duplicates: the algorithm behaves exactly like the plain subsets problem.
• Single element: return [[], [element]].

What should a senior engineer know?

The iterative and backtracking approaches are two ways to express the same duplicate-skip logic. The iterative approach tracks the previous round start index, while the backtracking approach uses i > index && nums[i] == nums[i-1] to skip. Both require sorting as a hard precondition.

In production, if the input size exceeds about 20, the output becomes impractically large (over a million subsets), so this problem is primarily algorithmic and interview-focused rather than a production pattern.