Subsets

Medium Problem 85 of 151 Java and Python

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The answer must not contain duplicate subsets and may be in any order.

Example 1

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

Example 2

Input: nums = [0]
Output: [[], [0]]

Constraints

1 ≤ nums.length ≤ 10
All numbers are unique.

Explanation

Each element is either in a subset or not: two choices per element, so there are 2ⁿ subsets.

Backtracking makes those choices one element at a time: add the current path to the answer, then try extending it with each later element, undoing the choice afterwards.

Approach 1 · Naive

Bitmasks

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

Count from 0 to 2ⁿ – 1. Bit i of the counter says whether nums[i] is in that subset.

For each mask from 0 to 2ⁿ - 1:
Build a subset with every nums[i] whose bit i is set.

Java

import java.util.*;

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

Python

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

Approach 2 · Optimal

Backtracking

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

Record the current path as a subset, then try adding each element after the last one used, recurse, and remove it again.

backtrack(start): add a copy of path to the result.
For i from start to n – 1: push nums[i], call backtrack(i + 1), pop.

Java

import java.util.*;

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

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

Python

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

        def backtrack(start):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

Complexity compared

Approach	Time	Space
Naive Bitmasks	O(n · 2ⁿ)	O(n) besides the output
Optimal Backtracking	O(n · 2ⁿ)	O(n) recursion besides the output

Key takeaways

Always add a copy of the path; the path itself keeps changing.
The start index is what stops [1, 2] and [2, 1] from both appearing.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem