78. Subsets

← All Problems
medium Backtracking
Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and may be returned in any order. For example, given [1,2,3], the output includes [], [1], [2], [3], [1,2], [1,3], [2,3], and [1,2,3].

Example

nums = [1, 2, 3]

Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

The power set contains all 2^3 = 8 possible subsets, from the empty set to the full set. Each element is either included or excluded, and no two subsets are the same.

For each element, you choose to include it or exclude it, building subsets recursively. At every step of the recursion, the current path is a valid subset, so add it to the results. The start index moves forward to avoid generating duplicate subsets.

Why this works

Every subset is a sequence of include/exclude decisions for each element. By recording the current path at every level of recursion (not just at the leaves), you capture subsets of all sizes. The start index ensures each element only appears after the ones before it, preventing duplicates like {1,2} and {2,1}.

Step by step

  1. Record the current path — at entry to each recursive call, the current path is a valid subset, so copy it into the results.
  2. Try adding each remaining element — loop from start to the end of the array. This ensures elements are always added in order.
  3. Recurse deeper — after adding nums[i], recurse with start = i + 1 so the next call only considers later elements.
  4. Backtrack — pop the last element off the path to undo the choice and try the next option.
Time: O(n·2ⁿ) Space: O(n) 
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)); // every partial path is a valid subset
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result); // move forward to avoid duplicates
            path.remove(path.size() - 1); // undo choice before trying next element
        }
    }
}

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

private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
        result.push_back(path); // every partial path is a valid subset
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, result); // move forward to avoid duplicates
            path.pop_back(); // undo choice before trying next element
        }
    }
};

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    def backtrack(start, path):
        result.append(path[:])  # every partial path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)  # move forward to avoid duplicate subsets
            path.pop()  # undo choice before trying the next element
    backtrack(0, [])
    return result