Get started

Subsets II — Medium Problem & Solution

nums is an integer array that may contain repeated values. Return every subset of it (its power set), with no subset appearing twice.

Problem statement

nums is an integer array that may contain repeated values. Return every subset of it (its power set), with no subset appearing twice. Two subsets are the same when they hold the same values with the same multiplicities, whichever positions they were taken from.

Write each subset in non-decreasing order, and list the subsets in lexicographic order: compare two subsets value by value from the left; when one is a prefix of the other, the shorter one comes first. So the empty subset is always first.

Example 1

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: Picking either of the two 2s gives the same subset `[1,2]`, so it is listed once.

Example 2

Input: nums = [0]
Output: [[],[0]]

Example 3

Input: nums = [4,4,1,4]
Output: [[],[1],[1,4],[1,4,4],[1,4,4,4],[4],[4,4],[4,4,4]]

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

How to solve Subsets II

After sorting, a subset is a non-decreasing sequence of values, and a subset is a duplicate exactly when the same value is chosen twice as the next element at the same depth. Skipping repeated values at each level removes every duplicate without a hash set.

Approach

  1. Sort nums.
  2. Run dfs(start) with a shared path: first append a copy of path to the answer.
  3. Then for every i from start to the end, skip it if i > start and nums[i] == nums[i - 1]; otherwise push nums[i], call dfs(i + 1), and pop.
  4. Call dfs(0) and return the collected subsets.

Why it works

Each distinct subset, written in sorted order, has exactly one leftmost way of being picked: for each value, take its copies from the earliest equal positions. The skip rule allows only that choice, so every subset is produced exactly once. The order is lexicographic because a subset is emitted before its extensions (a prefix comes first) and the children of a node are explored in increasing order of their next value.

Complexity

  • Time — O(n · 2^n)
  • Space — O(n) besides the output

Pitfalls

  • The skip test is i > start, not i > 0 — the first copy of a value at a new depth must still be usable, which is how [2,2] is formed.
  • Push a copy of path, not path itself, or every entry ends up as the same mutated list.
  • Without sorting, equal values are not adjacent and the skip rule misses duplicates.

Reference solution

Python

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    a = sorted(nums)
    out = []
    path = []

    def dfs(start):
        out.append(path[:])
        for i in range(start, len(a)):
            if i > start and a[i] == a[i - 1]:
                continue
            path.append(a[i])
            dfs(i + 1)
            path.pop()

    dfs(0)
    return out

JavaScript

var subsetsWithDup = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var out = [];
    var path = [];
    var dfs = function(start) {
        out.push(path.slice());
        for (var i = start; i < a.length; i++) {
            if (i > start && a[i] === a[i - 1]) continue;
            path.push(a[i]);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(0);
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation