Subsets II

Medium
1574.

Subsets II

Subsets II is a medium coding problem on arrays, bit manipulation and backtracking, asked in Amazon, Meta and Bloomberg interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subsets II — Solution in Python, Java & C++

Subsets II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Meta.

Subsets II is a medium coding problem on arrays, bit manipulation and backtracking, asked in Amazon, Meta and Bloomberg interviews.

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

Hints for Subsets II

  1. Hint 1

    Sort the array first, so equal values sit next to each other and every subset is built in non-decreasing order.

  2. Hint 2

    Build subsets by choosing which index comes next. Record the current subset every time you enter the recursion, before extending it.

  3. Hint 3

    At one level of the recursion, try each distinct value only once: skip index i when i > start and nums[i] == nums[i - 1]. Visiting the values in increasing order makes the output lexicographic for free.

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

Java

public static int[][] subsetsWithDup(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    List<int[]> out = new ArrayList<>();
    subsetsDfs(a, 0, new int[a.length], 0, out);
    return out.toArray(new int[0][]);
}

static void subsetsDfs(int[] a, int start, int[] path, int len, List<int[]> out) {
    out.add(Arrays.copyOf(path, len));
    for (int i = start; i < a.length; i++) {
        if (i > start && a[i] == a[i - 1]) continue;
        path[len] = a[i];
        subsetsDfs(a, i + 1, path, len + 1, out);
    }
}

C++

void subsetsDfs(vector<int>& a, int start, vector<int>& path, vector<vector<int>>& out) {
    out.push_back(path);
    for (int i = start; i < (int)a.size(); i++) {
        if (i > start && a[i] == a[i - 1]) continue;
        path.push_back(a[i]);
        subsetsDfs(a, i + 1, path, out);
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    vector<int> a(nums.begin(), nums.end());
    sort(a.begin(), a.end());
    vector<vector<int>> out;
    vector<int> path;
    subsetsDfs(a, 0, path, out);
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation