Subsets

Problem Description

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Examples

Constraints

• 1 ≤ nums.length ≤ 10
• -10 ≤ nums[i] ≤ 10
• All the numbers in nums are unique

Every Element Has Two Choices

The power set of n elements has exactly 2^n subsets because each element is either in a subset or it isn’t. That binary choice is the whole algorithm: for every element, decide to include it or skip it, then recurse on the rest.

The key is to collect the current subset at every node of the recursion tree, not just at the leaves. When you reach the end of the array, you’ve made all n decisions, but every intermediate state along the way is also a valid subset.

Solution 1: Backtracking

Build each subset by making an include/exclude decision at each index. Add the current subset to results at every call, then backtrack by removing the last element.

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> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current)); // snapshot at every node

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1); // undo the choice
        }
    }
}

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

        def backtrack(start: int, current: list[int]):
            result.append(current[:])  # snapshot at every node

            for i in range(start, len(nums)):
                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()  # undo the choice

        backtrack(0, [])
        return result

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }

private:
    void backtrack(std::vector<int>& nums, int start,
                   std::vector<int>& current,
                   std::vector<std::vector<int>>& result) {
        result.push_back(current); // snapshot at every node

        for (int i = start; i < (int)nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back(); // undo the choice
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n * 2^n). There are 2^n subsets and copying each takes O(n) in the worst case.
• Space Complexity: O(n) for the recursion stack depth. The output itself is O(n * 2^n).

Where it breaks: this solution assumes all elements are unique. If the input had duplicates, you’d get duplicate subsets without extra handling (see Subsets II for that variation).

Solution 2: Bit Manipulation

Each subset corresponds to a bitmask from 0 to 2^n - 1. Bit i being set means nums[i] is included.

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) { // bit i is set, include nums[i]
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }
}

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = []

        for mask in range(1 << n):
            subset = []
            for i in range(n):
                if mask & (1 << i):  # bit i is set, include nums[i]
                    subset.append(nums[i])
            result.append(subset)

        return result

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<std::vector<int>> result;

        for (int mask = 0; mask < (1 << n); mask++) {
            std::vector<int> subset;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) { // bit i is set, include nums[i]
                    subset.push_back(nums[i]);
                }
            }
            result.push_back(subset);
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n * 2^n). Same output size, same work.
• Space Complexity: O(n) extra, not counting output.

Where it breaks: 1 << n overflows a 32-bit integer at n = 32. With n ≤ 10 per the constraints this is fine, but if the problem ever extended to larger inputs, you’d need a 64-bit mask or switch back to backtracking.

Common Mistakes

• Not copying the current list before adding it. In Java and Python, result.add(current) adds a reference, not a copy. After backtracking, current is empty and your result list holds empty lists.
• Using i = 0 instead of i = start in the loop. Without start, you’d revisit earlier elements and generate duplicates like [1,2] and [2,1].
• Collecting results only at leaf nodes. Subsets include every intermediate state, not just the ones where you’ve reached the end of the array.

Frequently Asked Questions

How many subsets does an array of n elements have? Exactly 2^n. Each element is independently included or excluded. For n = 10, that’s 1024 subsets.

How does this differ from Combination Sum? Subsets generates all selections of any size with no repetition. Combination Sum generates selections that sum to a target, allowing element reuse.

What changes for Subsets II where elements can repeat? Sort the array first. In the backtracking loop, skip elements that equal the previous element at the same recursion depth. That one check eliminates all duplicate subsets.

← All Problems