Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Subsets II in Java: Unique Subsets Without Losing Repeated Values

Generate unique subsets with duplicates using sorted sibling choices, preserve repeated values inside subsets, and understand copying and undo.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Return all distinct subsets of an array that can contain duplicate values. Include the empty subset. For [1,2,2], [2,2] is valid, but [2] must appear only once.

The published LeetCode bounds allow 1–10 elements from −10 to 10. Output order is arbitrary. Negative values do not change the algorithm because it uses positions and equality, not sum pruning.

Constraints & requirements

CONTRACT
Verified bounds: 1–10 elements, values −10–10. Equal elements can both appear in a subset, but duplicate copies of the same subset must not appear. Input remains unchanged.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    [1,2,2]
    Output
    [[],[1],[1,2],[1,2,2],[2],[2,2]]

    Keep [2,2], but emit [2] only once.

  2. Example 2 Case 2

    Input
    [0]
    Output
    [[],[0]]

    A zero-valued singleton differs from the empty subset.

  3. Example 3 Case 3

    Input
    [2,2]
    Output
    [[],[2],[2,2]]

    Choosing zero, one or two copies gives three unique subsets.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Every prefix is already an answer; there is no target to wait for.

02Hint 2

Sort a copy, then skip equal next choices at the same level.

03Hint 3

Allow duplicates deeper in the path by testing i>start, not i>0.

How to think before coding

Every current prefix is a valid subset, so save it at entry, not only at a fixed leaf depth. The call’s start index prevents reusing a position. After sorting, skip equal nums[i] only when i>start; a repeated value at a deeper level may form [2,2] and is legal. Save a list copy, recurse at i+1, and remove the last chosen value.

Brute force and the improvement

Generate all 2^n index subsets, sort each value list or sort the input copy first, and deduplicate complete lists in a set. Selection/copy work takes O(n·2^n); the set may retain O(n·2^n) values in the all-distinct worst case. Sorting a copy and skipping equal choices at the SAME depth prevents duplicates before building them. Output remains exponential when all inputs differ; the benefit is avoiding duplicate subtrees when equal values occur.

Intuition: save every valid prefix

Unlike Combination Sum II, there is no target condition. [], [1] and [1,2] are all complete answers, even if we can extend them. Save a copy as soon as a recursive call starts.

Sorting brings duplicate values together. At the root, the first 2 can begin [2]; starting again with the second 2 would repeat the same value list. Skip that equivalent sibling. Deeper in the first 2 branch, the second 2 is still available and creates [2,2].

Think “skip equivalent next choices,” not “ban repeated numbers.” That is why removing duplicates from the input is wrong.

Algorithm

  1. Sort a copy of the array.
  2. Save a copy of the current path, including the initial empty path.
  3. Try the next position from start onward.
  4. Skip it when it equals the previous value and i is greater than this call’s start.
  5. Append, recurse from i+1, then undo the append.

Java solution

Sort a copy, save a path copy at entry, skip duplicate sibling choices and recurse from the next index. These operations preserve repeated values inside a legitimate subset.

Java
import java.util.*;

class Solution {
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        int[] sorted = nums.clone(); // Sorting a copy avoids changing the input.
        Arrays.sort(sorted); // Equal values must be adjacent for sibling duplicate skipping.
        List<List<Integer>> result = new ArrayList<>();
        uniqueSubsets(sorted, 0, new ArrayList<>(), result);
        return result;
    }
    private static void uniqueSubsets(int[] nums, int start,
            List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path)); // EVERY prefix is a subset, including the empty one.
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // Equal values at this level make duplicates.
            path.add(nums[i]); // A deeper copy of the same value is still allowed.
            uniqueSubsets(nums, i + 1, path, result); // Use each array position at most once.
            path.remove(path.size() - 1); // Undo for the next sibling; saved copies do not change.
        }
    }

    public static void main(String[] args) {
        System.out.println(subsetsWithDup(new int[]{1, 2, 2})); // [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
    }
}

The default invocation returns [[],[1],[1,2],[1,2,2],[2],[2,2]]. Copies in the result survive subsequent backtracking.

Recursion tree and dry run

Numbered illustrated dry run for Subsets II; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: nums = [1,2,2]

What to track: Track start and path. Every entered call saves its prefix. Equal siblings are skipped, but the second 2 remains available in a deeper call.

  1. Save the empty prefix

    Java operationresult.add(new ArrayList<>(path));
    Statestart = 0; path = []; result = [[]]

    Unlike target-sum enumeration, every prefix is an answer, including the root.

  2. Choose 1 and then the first 2

    Java operationuniqueSubsets(nums, i + 1, path, result);
    Stateentered prefixes: [1] at start = 1, then [1,2] at start = 2

    Each entered call saves a copy before exploring its remaining positions.

  3. Allow the deeper equal value

    Java operationif (i > start && nums[i] == nums[i - 1]) continue;
    Statestart = 2; i = 2; equality exists but i > start is false; save [1,2,2]

    This second 2 extends the first 2; it is not a duplicate sibling branch.

  4. Undo before the sibling check

    Java operationpath.remove(path.size() - 1);
    Statereturn restores [1,2], then [1]; the start = 1 frame resumes with i = 2

    Now i > start and the equal previous 2 make this sibling a duplicate, so it is skipped.

  5. Explore the root’s first 2

    Java operationuniqueSubsets(nums, i + 1, path, result);
    Stateroot chooses index 1: save [2]; its child chooses index 2: save [2,2]

    These prefixes do not contain 1, so they are new subsets.

  6. Finish the root

    Java operationif (i > start && nums[i] == nums[i - 1]) continue;
    Stateroot i = 2 is skipped; path = []; six saved snapshots remain

    A second root-level [2] branch would duplicate the previous root branch. Saved copies survive every undo.

Final result: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Worked example · read from top to bottom
[] → save
├─ choose 1: [1] → save
│  ├─ choose first 2: [1,2] → save
│  │  └─ choose second 2: [1,2,2] → save
│  └─ second 2 as sibling → skip
├─ choose first 2: [2] → save
│  └─ choose second 2: [2,2] → save
└─ second 2 as root sibling → skip
Before choice Action After returning and undoing
[] Add 1 and explore []
[1] Add first 2 and explore [1]
[1,2] Add second 2 and save [1,2]
[] Add first 2 and explore []

The call stack pop and path removal are different events: first the child finishes, then the resumed parent removes its temporary choice.

Why it works

The path follows increasing input indices, so no position is selected twice. Every valid subset has a sorted value representation. At each level, choosing the first available occurrence of its next value leaves the remaining copies available below it. Equivalent later sibling occurrences add nothing new. Consequently all distinct value subsets appear once.

Complexity and alternative approaches

Worst-case time is O(N·2^N), including subset copies, plus O(N log N) sorting. With all distinct values, every subset is produced. Auxiliary space is O(N), including the input copy, path and stack; output can take O(N·2^N).

If value groups have counts c₁, c₂, …, the number of distinct subsets is U = ∏(cᵢ+1): choose zero through cᵢ copies of each value. The total size of those U returned lists describes output cost more precisely than only counting them.

Alternatives include generating all index subsets and deduplicating canonical lists, or branching by how many copies of each value group to take. The sibling-skip version avoids an output-sized deduplication set.

Common mistakes

  • Forgetting the empty subset.
  • Testing i > 0, which incorrectly skips repeated values in deeper calls.
  • Using a global visited-value set, which loses [2,2].
  • Saving the shared path object instead of a copy.
  • Waiting until index reaches the end without designing an include/skip tree; the loop-prefix method saves at entry.

Practice next

Next lessonPower Set for distinct values

Back to Recursion and backtracking →