Subsets

MEDIUM✓ CHIP-TIMEDLC #78 — FULL STATEMENT ↗

The drill: Every possible group you can pull from an array, including the empty group and the whole array itself, with each item used at most once — return all of them.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of distinct numbers arrives, and the job is to list every group that can be pulled from it — every possible subset, not just ones that satisfy some condition.

The empty group counts as one of the results, and so does the full array itself. Every element appears in some subsets and is left out of others, but within a single subset no element repeats.

The order of the groups in the output and the order of elements inside each group don't matter — what matters is that every distinct subset shows up exactly once.

EX 01

nums = [5]

→ [[], [5]]

MINIMUM SIZE

EX 02

nums = [1, 2]

→ [[], [1], [2], [1, 2]]

EX 03

nums = [1, 2, 3]

→ [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

CLASSIC N = 3

arrays are short — usually well under twenty elements, since the output size is exponential
all elements in the input are distinct
the empty subset and the full array both belong in the output
output order and within-group order are both free

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

There's no filtering condition here — the challenge is coverage, not selection. Think about what choice you make once for every single element.

HINT 2 THE STRUCTURE

Each element has exactly two states: in the group or out of it. n elements, two states each, gives every subset a unique fingerprint of yes/no answers.

HINT 3 ONE STEP FROM THE ANSWER

Recurse element by element: at each one, branch into 'include it and recurse' and 'skip it and recurse'. When you've decided for all n elements, the current path is one full subset.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE IN-OR-OUT TREEPATTERN · INCLUDE OR SKIP, BACKTRACKnums = [1, 2]

STEP 1

Two numbers, 1 and 2. Backtrack decides in-or-out for each one — every leaf of this tree is a different subset.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/subsets.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        n = len(nums)

        def backtrack(i):
            if i == n:
                res.append(list(path))
                return
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
            backtrack(i + 1)

        backtrack(0)
        return res

TIME O(N·2ⁿ)SPACE O(N)PYTHON · RACE PACE · 17 LN

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        for mask in range(1 << n):
            cur = []
            for i in range(n):
                if mask & (1 << i):
                    cur.append(nums[i])
            res.append(cur)
        return res

TIME O(N·2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int i, List<Integer> path, List<List<Integer>> res) {
        if (i == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
        backtrack(nums, i + 1, path, res);
    }
}

TIME O(N·2ⁿ)SPACE O(N)JAVA · RACE PACE · 18 LN

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

TIME O(N·2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED