Subsets

Problem

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

Constraints

• 1 ≤ nums.length ≤ 10
• all integers unique

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def subsets(self, nums):
        res = []
        def bt(start, cur):
            res.append(cur[:])
            for i in range(start, len(nums)):
                cur.append(nums[i])
                bt(i + 1, cur)
                cur.pop()
        bt(0, [])
        return res

Java

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

    private void backtrack(List<List<Integer>> result, List<Integer> current,
                           int[] nums, int start) {
        // Every prefix of the recursion is itself a valid subset.
        result.add(new ArrayList<>(current));
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(result, current, nums, i + 1);
            current.remove(current.size() - 1);
        }
    }
}

// Bitmask alternative: every subset corresponds to an n-bit number —
// loop mask from 0 to 2^n - 1 and take element i when (mask >> i & 1) == 1.

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.