Subsets LeetCode Solution: Three Approaches to #78

Subsets leetcode problem #78 is the first backtracking problem most engineers encounter on the NeetCode roadmap, and for good reason. It strips away all the complexity of more advanced backtracking problems and gives you the purest version of the core decision: for each element, do you include it or skip it?

Once you internalize this include-or-exclude pattern, problems like Permutations (#46), Combination Sum (#39), and Subsets II (#90) become variations on the same theme rather than entirely new challenges. That is why mastering this single problem unlocks an entire category of interview questions.

In this walkthrough, we will cover three distinct approaches to generating the power set: backtracking with recursion, an iterative build-up method, and a bit manipulation technique that maps subsets to binary numbers. Each approach runs in O(n * 2^n) time, but they exercise different problem-solving muscles that interviewers value.

The problem statement is straightforward: given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and you can return the answer in any order.

For example, given nums = [1, 2, 3], the output is [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]. That is 2^3 = 8 subsets in total. For an array of n distinct elements, there are always exactly 2^n subsets because each element is either included or excluded.

This is exactly the definition of the power set from discrete mathematics. The key insight is that the number of subsets grows exponentially with the input size, so any correct solution must be at least O(2^n) — there is no shortcut around generating all of them.

The backtracking approach models the problem as a binary decision tree. At each level of the tree, you decide whether to include or exclude the current element. When you have made a decision for every element, you have reached a leaf node — a complete subset.

You start with an empty current subset and an index pointing to the first element. At each recursive call, you add the current state to your result (every node in the tree represents a valid subset, not just leaves). Then you loop from the current index forward, adding each element to your subset, recursing deeper, and then removing the element (backtracking) to explore the next branch.

The time complexity is O(n * 2^n) because there are 2^n subsets and copying each subset into the result takes O(n) time. The space complexity is O(n) for the recursion stack depth, not counting the output storage.

The iterative approach is arguably the most elegant solution to the subsets leetcode problem. You start with a result containing only the empty subset: [[]]. Then for each number in the input array, you take every existing subset in the result, make a copy with the new number appended, and add all those new subsets back to the result.

For nums = [1, 2, 3], the process unfolds like this. Start with [[]]. Process 1: copy [] and add 1 to get [1], result is now [[], [1]]. Process 2: copy [] and [1], add 2 to each to get [2] and [1,2], result is now [[], [1], [2], [1,2]]. Process 3: copy all four and add 3, result is the complete power set with 8 subsets.

This approach has the same O(n * 2^n) time complexity as backtracking, but it avoids recursion entirely. The space complexity is O(1) beyond the output itself, making it slightly more memory-efficient. Many engineers find this approach easier to implement correctly under interview pressure because there is no recursive state to manage.

The bit manipulation approach exploits a direct mapping between subsets and binary numbers. For an array of n elements, every integer from 0 to 2^n - 1 can be represented as an n-bit binary number. Each bit position corresponds to an element in the array: if the bit is 1, include that element; if 0, exclude it.

For nums = [1, 2, 3], the binary number 101 (which is 5 in decimal) maps to the subset [1, 3] because the first and third bits are set. The number 000 maps to the empty set, and 111 maps to [1, 2, 3]. You simply iterate from 0 to 2^n - 1 and construct each subset by checking which bits are set.

This approach also runs in O(n * 2^n) time. It is particularly elegant for interviews because the implementation is concise and demonstrates comfort with bitwise operations. However, it only works when n is small enough that 2^n fits in an integer — which is always the case for this problem given the constraint n <= 10.

The edge cases for subsets leetcode #78 are minimal but worth knowing. An empty array returns [[]]. A single-element array [x] returns [[], [x]]. Since the problem guarantees distinct elements, you never need to worry about deduplication in the basic version.

The natural follow-up is Subsets II (#90), where the input array can contain duplicates. For example, [1, 2, 2] should produce [[], [1], [2], [1,2], [2,2], [1,2,2]] — notice there is only one [2], not two. The trick is to sort the array first and then skip duplicates at the same decision level during backtracking, the same technique used in 3Sum and Combination Sum II.

In interviews, expect the interviewer to ask about Subsets II as a follow-up after you solve #78. Having the sort-and-skip pattern ready shows depth of understanding beyond memorized solutions.

The include/exclude decision pattern from subsets is the backbone of nearly every backtracking and recursive enumeration problem on LeetCode. Once you see that Permutations is "choose which unused element goes next" and Combination Sum is "include this candidate again or move on," you realize they are all variations of the same binary choice tree.

Practicing subsets also builds your intuition for exponential time complexity. When you see 2^n in a problem constraint (like n <= 20), it is a strong hint that the intended solution enumerates all subsets or uses bitmask DP. Recognizing this signal saves you from overcomplicating the approach.

If you are preparing for coding interviews, make this problem your first stop in the backtracking category. Solve it with all three approaches, understand why each works, and then move on to Subsets II, Permutations, and Combination Sum. YeetCode flashcards can help you drill the include/exclude pattern through spaced repetition so it becomes automatic during your interview.