šŸ”— LeetCode

Subsets

MediumbacktrackingAmazonMicrosoftMetaGoogleBloombergApple

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

Input:nums = [1,2,3]
Output:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Explanation:All 8 subsets of [1, 2, 3] formed by exploring inclusion and exclusion choices.
Input:nums = [0]
Output:[[],[0]]
Explanation:A single element array has two subsets: the empty set and the single element set.
Input:nums = [1,2]
Output:[[],[1],[2],[1,2]]
Explanation:All 4 subsets of [1, 2]: empty set [], singletons [1] and [2], and pair [1, 2]. This matches the step-by-step decision tree dry run.

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

šŸ’” Hints

Hint 1

At each step in recursion, you can choose to include or exclude an element.

Hint 2

Use backtracking: append current element to path, recurse for remaining elements, then backtrack (pop).

Hint 3

Every node visited in the decision tree represents a valid subset.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Exponential
Algorithmic Approach

Backtracking / DFS state-space tree traversal. At each step, copy current subset into result, then iterate through remaining choices, push, recurse, and pop.

Time ComplexityO(N * 2^N)
Why:

There are 2^N total subsets for N elements; each subset requires up to O(N) time to construct and copy into results.

Space ComplexityO(N)
Why:

Backtracking recursion call stack and current subset path array consume at most O(N) auxiliary space.

Big-O Growth CurveExponential (O(2āæ))
Operations double with each additional element; suitable only for small N.

šŸŒ Real-World Use Cases

AirbnbDynamic Filter Combinations & Amenity Search

Enumerating all combinations of active amenity and feature filters (Wi-Fi, pool, kitchen) to generate cache keys and evaluate pricing matching subsets.

šŸ” Dry Run

Solutionā± O(N * 2^N) | šŸ’¾ O(N)
Backtracking / State Space Tree
Recursion Stack
Active State
Valid Solution
Backtrack / Pop
Current Path:
[] (root state)
ā–¼ backtrack(0)
[]success
Solutions Collected (1):
[]
Line6
startIndex=0number
current=[]array
result.length=1number

Call backtrack(0) with empty path current = []. Save [] to result.