Command Palette

Search for a command to run...

Hectal
Problem 13.2 · BacktrackingMedium

Subsets II

PatternBacktracking

What it teaches: Duplicates in the input: sort, then skip equal values at the same depth.

Practise it on judges as “Subsets II”.

The problem

Given an array that may contain duplicates, return all subsets without duplicate subsets, in any order.

Example 1

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

Constraints

  • 1 ≤ nums.length ≤ 10

Pattern clues in the wording

  • → "All subsets" + duplicates in the input + no duplicate answers

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [1,2,2]
[[],[1],[1,2],[1,2,2],[2],[2,2]]
2
nums = [0]
[[],[0]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Sorted backtracking with a skip · O(n · 2ⁿ)
1

Sorted backtracking with a skip

Time O(n · 2ⁿ) Space O(n)

Same as Subsets, after sorting, with if (i > start && nums[i] == nums[i − 1]) continue;.

Approach 1
import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), out);
        return out;
    }

    private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
        out.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            dfs(nums, i + 1, path, out);
            path.remove(path.size() - 1);
        }
    }
}

Verdict: Generates each distinct subset exactly once.

Before you submit

Edge cases and common mistakes

Test these inputs

  • All elements equal
  • No duplicates (same as Subsets)

Mistakes people make

  • Not sorting first.
  • Skipping with i > 0.

Interview

Follow-up questions

Why does i > start keep [2, 2]?