Subsets - Solution & Explanation

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.