78. Subsets - Solution & Explanation

Q: Is Subsets easy or hard?

Subsets is generally classified as a medium-level problem. The concept is straightforward, but it tests whether you recognize the power set pattern and implement recursive backtracking or bit masking correctly.

Q: Subsets Python/Java solution

In Python or Java, the typical solution uses recursive backtracking. Start with an empty list, recursively add elements from the array, and store each intermediate subset. Both languages also support a bit manipulation approach that iterates from 0 to (1 << n) - 1 and checks bits to build subsets.

Q: How to solve Subsets in O(n)?

Generating all subsets cannot be done in O(n) because the output itself contains 2^n subsets. The optimal algorithms—backtracking or bit manipulation—run in O(n * 2^n) time, which matches the size of the result set and is considered optimal for this problem.

Q: What is the best approach for Subsets?

Recursive backtracking is the most common approach for the Subsets problem. It explores the decision tree where each element can be either included or excluded. The algorithm generates all 2^n subsets with O(n * 2^n) time complexity and O(n) recursion space, making it both intuitive and flexible for interview variations.

Q: Is Subsets asked at Google/Amazon/Meta?

Subsets and related power set problems frequently appear in technical interviews at companies like Amazon, Google, Meta, and Microsoft. Interviewers use it to test recursion, backtracking, and understanding of combinatorial enumeration.

Q: What data structure is used in Subsets?

The main data structure is an array or list to store the current subset during generation. Backtracking uses recursion with a dynamic list, while the bit manipulation approach uses integers as binary masks to represent subset membership.

Q: What is the time complexity of Subsets?

The time complexity is O(n * 2^n). There are 2^n possible subsets for an array of size n, and building each subset can take up to O(n) time when copying elements into the result list.

The problem

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.

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
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Approach overview

Problem Overview: Given an integer array nums, generate every possible subset (the power set). Each element can either be included or excluded, so for n numbers there are 2^n total subsets. The challenge is systematically exploring all combinations without duplicates.

Approach 1: Recursive Backtracking (Time: O(n * 2^n), Space: O(n))

Backtracking builds subsets incrementally. Start with an empty subset, then recursively decide whether to include each element. At every recursion level, append the current subset to the result and iterate through remaining elements. For each element, add it to the current subset, recurse deeper, then remove it (backtrack) before exploring the next option.

This method naturally explores the decision tree where each element represents a branch: include or skip. The recursion depth is at most n, and each subset creation costs up to O(n) to copy elements. Since there are 2^n subsets, the total time becomes O(n * 2^n). This pattern appears frequently in backtracking problems where you enumerate combinations or permutations.

Backtracking is intuitive and easy to extend. If constraints change (for example, subsets with a specific size or sum), you can add pruning conditions inside the recursion. This flexibility makes it the most common interview implementation.

Approach 2: Bit Manipulation (Time: O(n * 2^n), Space: O(1) extra)

Every subset can be represented as a binary mask. For an array of length n, numbers from 0 to (1 << n) - 1 cover all possible inclusion patterns. Each bit in the mask indicates whether the corresponding element is present in the subset.

Iterate through all masks and check each bit position. If the j-th bit is set in mask i, include nums[j] in the current subset. This produces every subset in lexicographic mask order. The loop runs 2^n times and checks n bits per mask, leading to O(n * 2^n) time.

This technique relies on simple bit operations like (mask & (1 << j)). It's common in problems involving subset enumeration and is closely related to bit manipulation patterns. When working with small arrays, it provides a clean iterative alternative to recursion.

Recommended for interviews: Recursive backtracking is the approach most interviewers expect because it demonstrates your understanding of recursion trees and subset generation patterns. It also adapts easily to variations of the problem. Bit manipulation is a strong alternative when you want a compact iterative solution or when discussing subset representation using binary masks. Both rely on the same core observation: each element has two states, giving 2^n total subsets for an array of length n.

Approach 1: Recursive Backtracking

This approach utilizes the concept of recursive backtracking to explore all potential subsets. We start with an empty list and progressively build subsets by either including or excluding each element.

Python

class Solution:
    def subsets(self, nums):
        result = []
        self.backtrack(nums, 0, [], result)
        return result

    def backtrack(self, nums, index, current, result):
        result.append(list(current))
        for i in range(index, len(nums)):
            current.append(nums[i])
            self.backtrack(nums, i + 1, current, result)
            current.pop()

sol = Solution()
nums = [1, 2, 3]
print(sol.subsets(nums))

Java

import java.util.ArrayList;
import java.util.List;

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

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = sol.subsets(nums);

        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

C++

#include <iostream>
#include <vector>

class Solution {
public:
    void backtrack(std::vector<int>& nums, std::vector<std::vector<int>>& result, std::vector<int>& current, int start) {
        result.push_back(current);
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(nums, result, current, i + 1);
            current.pop_back();
        }
    }

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

int main() {
    Solution sol;
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> result = sol.subsets(nums);

    for (const auto& subset : result) {
        std::cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            std::cout << subset[i];
            if (i < subset.size() - 1) std::cout << ", ";
        }
        std::cout << "]\n";
    }
    return 0;
}

JavaScript

const subsets = (nums) => {
    const result = [];
    const backtrack = (index, current) => {
        result.push([...current]);
        for (let i = index; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    };
    backtrack(0, []);
    return result;
};

const nums = [1, 2, 3];
console.log(subsets(nums));

#include <stdio.h>
#include <stdlib.h>

void backtrack(int* nums, int numsSize, int** subsets, int* subset, int start, int* returnSize, int** returnColumnSizes) {
    subsets[*returnSize] = (int*)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < start; i++) {
        subsets[*returnSize][i] = subset[i];
    }
    (*returnColumnSizes)[*returnSize] = start;
    (*returnSize)++;

    for (int i = start; i < numsSize; i++) {
        subset[start] = nums[i];
        backtrack(nums, numsSize, subsets, subset, start + 1, returnSize, returnColumnSizes);
    }
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int maxSize = 1 << numsSize;
    int** subsets = (int**)malloc(maxSize * sizeof(int*));
    int* subset = (int*)malloc(numsSize * sizeof(int));
    *returnColumnSizes = (int*)malloc(maxSize * sizeof(int));
    *returnSize = 0;

    backtrack(nums, numsSize, subsets, subset, 0, returnSize, returnColumnSizes);

    free(subset);
    return subsets;
}

int main() {
    int nums[] = {1, 2, 3};
    int size = 3;
    int returnSize;
    int* returnColumnSizes;
    int** result = subsets(nums, size, &returnSize, &returnColumnSizes);

    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(", ");
        }
        printf("]\n");
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        Backtrack(nums, result, new List<int>(), 0);
        return result;
    }

    private void Backtrack(int[] nums, IList<IList<int>> result, List<int> current, int start) {
        result.Add(new List<int>(current));
        for (int i = start; i < nums.Length; i++) {
            current.Add(nums[i]);
            Backtrack(nums, result, current, i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3};
        var result = sol.Subsets(nums);

        foreach (var subset in result) {
            Console.WriteLine("[" + string.Join(", ", subset) + "]");
        }
    }
}

This Python solution uses recursive backtracking. The main function generates a list 'result' to accumulate the results, and the backtracking function explores the subsets by deciding to include or exclude each element.

Complexity

Time Complexity: O(2^n * n), reflecting the number of subsets and the time needed to create them.
Space Complexity: O(n), for using the recursion stack.

Try this approach in the editor

Approach 2: Bit Manipulation

This approach takes advantage of bit manipulation to enumerate subsets. Each subset can correspond to a binary number where each bit decides if an element is present in the subset:

Python

def subsets(nums):
    subset_count = 1 << len(nums)
    result = []
    for i in range(subset_count):
        subset = []
        for j in range(len(nums)):
            if i & (1 << j):
                subset.append(nums[j])
        result.append(subset)
    return result

nums = [1, 2, 3]
print(subsets(nums))

Java

import java.util.ArrayList;
import java.util.List;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = sol.subsets(nums);
        System.out.println(result);
    }
}

C++

#include <iostream>
#include <vector>

std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
    int subsetCount = 1 << nums.size();
    std::vector<std::vector<int>> result;
    for (int i = 0; i < subsetCount; ++i) {
        std::vector<int> subset;
        for (int j = 0; j < nums.size(); ++j) {
            if (i & (1 << j)) {
                subset.push_back(nums[j]);
            }
        }
        result.push_back(subset);
    }
    return result;
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> result = subsets(nums);

    for (const auto& subset : result) {
        std::cout << "[";
        for (int num : subset) {
            std::cout << num << " ";
        }
        std::cout << "]\n";
    }
    return 0;
}

JavaScript

const subsets = (nums) => {
    const result = [];
    const subsetCount = 1 << nums.length;
    for (let i = 0; i < subsetCount; i++) {
        const subset = [];
        for (let j = 0; j < nums.length; j++) {
            if (i & (1 << j)) {
                subset.push(nums[j]);
            }
        }
        result.push(subset);
    }
    return result;
};

const nums = [1, 2, 3];
console.log(subsets(nums));

#include <stdio.h>
#include <math.h>

void subsets(int* nums, int numsSize) {
    int subsetCount = pow(2, numsSize);
    for (int i = 0; i < subsetCount; i++) {
        printf("[");
        for (int j = 0; j < numsSize; j++) {
            if (i & (1 << j)) {
                printf("%d ", nums[j]);
            }
        }
        printf("]\n");
    }
}

int main() {
    int nums[] = {1, 2, 3};
    int size = 3;
    subsets(nums, size);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        int subsetCount = 1 << nums.Length;
        for (int i = 0; i < subsetCount; i++) {
            List<int> subset = new List<int>();
            for (int j = 0; j < nums.Length; j++) {
                if ((i & (1 << j)) > 0) {
                    subset.Add(nums[j]);
                }
            }
            result.Add(subset);
        }
        return result;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3};
        var result = sol.Subsets(nums);

        foreach (var subset in result) {
            Console.WriteLine("[" + string.Join(", ", subset) + "]");
        }
    }
}

Python's implementation leverages bitwise operations to enumerate all subsets. Each number from 0 to 2^n - 1 represents a potential subset, interpreted by binary bit positions for index responses.

Complexity

Time Complexity: O(2^n * n), for acquisition of each subset.
Space Complexity: O(1), nonadditional storage used herein.

Try this approach in the editor

Approach 3: DFS (Backtracking)

We design a function dfs(i), which represents starting the search from the ith element of the array for all subsets. The execution logic of the function dfs(i) is as follows:

If i = n, it means the current search has ended. Add the current subset t to the answer array ans, and then return.
Otherwise, we can choose not to select the current element and directly execute dfs(i + 1); or we can choose the current element, i.e., add the current element nums[i] to the subset t, and then execute dfs(i + 1). Note that we need to remove nums[i] from the subset t after executing dfs(i + 1) (backtracking).

In the main function, we call dfs(0), i.e., start searching all subsets from the first element of the array. Finally, return the answer array ans.

The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the array. There are a total of 2^n subsets, and each subset takes O(n) time to construct.

TypeScript

function subsets(nums: number[]): number[][] {
    const ans: number[][] = [];
    const t: number[] = [];
    const dfs = (i: number) => {
        if (i === nums.length) {
            ans.push(t.slice());
            return;
        }
        dfs(i + 1);
        t.push(nums[i]);
        dfs(i + 1);
        t.pop();
    };
    dfs(0);
    return ans;
}

func subsets(nums []int) (ans [][]int) {
	t := []int{}
	var dfs func(int)
	dfs = func(i int) {
		if i == len(nums) {
			ans = append(ans, append([]int(nil), t...))
			return
		}
		dfs(i + 1)
		t = append(t, nums[i])
		dfs(i + 1)
		t = t[:len(t)-1]
	}
	dfs(0)
	return
}

Rust

impl Solution {
    fn dfs(i: usize, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
        if i == nums.len() {
            ans.push(t.clone());
            return;
        }
        Self::dfs(i + 1, t, ans, nums);
        t.push(nums[i]);
        Self::dfs(i + 1, t, ans, nums);
        t.pop();
    }

    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut ans = Vec::new();
        Self::dfs(0, &mut Vec::new(), &mut ans, &nums);
        ans
    }
}

Try this approach in the editor

Approach 4: Binary Enumeration

We can also use the method of binary enumeration to get all subsets.

We can use 2^n binary numbers to represent all subsets of n elements. For the current binary number mask, if the ith bit is 1, it means that the ith element is selected, otherwise it means that the ith element is not selected.

The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the array. There are a total of 2^n subsets, and each subset takes O(n) time to construct.

TypeScript

function subsets(nums: number[]): number[][] {
    const n = nums.length;
    const ans: number[][] = [];
    for (let mask = 0; mask < 1 << n; ++mask) {
        const t: number[] = [];
        for (let i = 0; i < n; ++i) {
            if (((mask >> i) & 1) === 1) {
                t.push(nums[i]);
            }
        }
        ans.push(t);
    }
    return ans;
}

func subsets(nums []int) (ans [][]int) {
	n := len(nums)
	for mask := 0; mask < 1<<n; mask++ {
		t := []int{}
		for i, x := range nums {
			if mask>>i&1 == 1 {
				t = append(t, x)
			}
		}
		ans = append(ans, t)
	}
	return
}

Rust

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut ans = Vec::new();
        for mask in 0..(1 << n) {
            let mut t = Vec::new();
            for i in 0..n {
                if (mask >> i) & 1 == 1 {
                    t.push(nums[i]);
                }
            }
            ans.push(t);
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Backtracking	Time Complexity: O(2^n * n), reflecting the number of subsets and the time needed to create them. Space Complexity: O(n), for using the recursion stack.
Bit Manipulation	Time Complexity: O(2^n * n), for acquisition of each subset. Space Complexity: O(1), nonadditional storage used herein.
DFS (Backtracking)	–
Binary Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Backtracking	O(n * 2^n)	O(n) recursion stack	General subset generation and when the problem may add constraints like size, sum, or conditions
Bit Manipulation (Binary Mask)	O(n * 2^n)	O(1) extra	When you want an iterative solution or need to represent subsets efficiently using binary masks

Frequently asked questions

Is Subsets easy or hard?

Subsets is generally classified as a medium-level problem. The concept is straightforward, but it tests whether you recognize the power set pattern and implement recursive backtracking or bit masking correctly.

Subsets Python/Java solution

In Python or Java, the typical solution uses recursive backtracking. Start with an empty list, recursively add elements from the array, and store each intermediate subset. Both languages also support a bit manipulation approach that iterates from 0 to (1 << n) - 1 and checks bits to build subsets.

How to solve Subsets in O(n)?

Generating all subsets cannot be done in O(n) because the output itself contains 2^n subsets. The optimal algorithms—backtracking or bit manipulation—run in O(n * 2^n) time, which matches the size of the result set and is considered optimal for this problem.

What is the best approach for Subsets?

Recursive backtracking is the most common approach for the Subsets problem. It explores the decision tree where each element can be either included or excluded. The algorithm generates all 2^n subsets with O(n * 2^n) time complexity and O(n) recursion space, making it both intuitive and flexible for interview variations.

Is Subsets asked at Google/Amazon/Meta?

Subsets and related power set problems frequently appear in technical interviews at companies like Amazon, Google, Meta, and Microsoft. Interviewers use it to test recursion, backtracking, and understanding of combinatorial enumeration.

What data structure is used in Subsets?

The main data structure is an array or list to store the current subset during generation. Backtracking uses recursion with a dynamic list, while the bit manipulation approach uses integers as binary masks to represent subset membership.

What is the time complexity of Subsets?

The time complexity is O(n * 2^n). There are 2^n possible subsets for an array of size n, and building each subset can take up to O(n) time when copying elements into the result list.

Subsets solution and explanation

The problem

Approach overview

Approach 1: Recursive Backtracking

Approach 2: Bit Manipulation

Approach 3: DFS (Backtracking)

Approach 4: Binary Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Subsets solution and explanation

The problem

Approach overview

Approach 1: Recursive Backtracking

Approach 2: Bit Manipulation

Approach 3: DFS (Backtracking)

Approach 4: Binary Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems