Problem 13.1 · BacktrackingMedium

Subsets

What it teaches: The base template: record every path, extend only with later elements.

Practise it on judges as “Subsets”.

The problem

Given an array of distinct integers, return all possible subsets (the power set), in any order.

Example 1

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

Constraints

1 ≤ nums.length ≤ 10
Distinct values

Pattern clues in the wording

→ "All subsets"
→ n ≤ 10: 2ⁿ answers is fine

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>> subsets(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

#	Input	Expected
1	nums = [1,2,3]	[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
2	nums = [0]	[[],[0]]

From slow to fast

Approaches

1. Backtracking with a start index · O(n · 2ⁿ)2. Bitmask enumeration · O(n · 2ⁿ)

Backtracking with a start index

Time O(n · 2ⁿ) Space O(n) recursion besides the output

Record the current path at every call, then for i from start add nums[i], recurse with i + 1, and remove it.

Approach 1

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] 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++) {
            path.add(nums[i]);
            dfs(nums, i + 1, path, out);
            path.remove(path.size() - 1);
        }
    }
}

Verdict: The standard answer.

Bitmask enumeration

Time O(n · 2ⁿ) Space O(1) besides the output

Every number from 0 to 2ⁿ − 1 is a subset: bit i says whether nums[i] is in it.

Approach 2

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        for (int mask = 0; mask < (1 << nums.length); mask++) {
            List<Integer> s = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) if ((mask & (1 << i)) != 0) s.add(nums[i]);
            out.add(s);
        }
        return out;
    }
}

Verdict: Iterative and neat; works because n is small.

Before you submit

Edge cases and common mistakes

Test these inputs

One element
Negative numbers

Mistakes people make

Adding path without copying.

Interview

Follow-up questions

How would you generate subsets of size exactly k?

Command Palette