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] <= 10nums are unique.Problem Overview: Given an integer array nums, generate every possible subset (the power set). Each element can either be included or excluded, so the result contains 2^n subsets for an array of size n. The challenge is systematically exploring all combinations without duplicates.
Approach 1: Recursive Backtracking (Time: O(n * 2^n), Space: O(n))
This method builds subsets incrementally using backtracking. Start with an empty subset and recursively decide whether to include each element. At every recursion level, append the current subset to the result and iterate through remaining elements. Add an element, recurse deeper, then remove it (backtrack) to explore the next possibility. Because each element branches into two choices (include or skip), the algorithm generates 2^n subsets, and copying subsets contributes an additional O(n) factor.
Backtracking is easy to reason about and closely mirrors how humans think about combinations. You explicitly explore the decision tree: choose an element, continue building, then undo the choice. This approach generalizes well to many interview problems involving combinations, permutations, or constraint exploration.
Approach 2: Bit Manipulation (Time: O(n * 2^n), Space: O(1) auxiliary)
Every subset of an array can be represented by a binary mask. For an array of length n, numbers from 0 to (1 << n) - 1 represent all subset combinations. Each bit indicates whether an element is included: if the i-th bit is set, include nums[i] in the current subset. Iterate through all masks and check each bit using bit operations like mask & (1 << i). This approach leverages concepts from bit manipulation and avoids recursion entirely.
The insight is that the power set size is exactly 2^n, which matches the number of binary numbers with n bits. Each binary representation acts as a blueprint describing which elements belong to the subset. Iterating through masks guarantees every combination appears exactly once.
Recommended for interviews: Recursive backtracking is the most commonly expected solution. It demonstrates mastery of recursion, state exploration, and pruning patterns common in array combination problems. Bit manipulation is equally optimal in time complexity but is typically presented as an alternative or optimization mindset. Showing both approaches signals strong algorithmic flexibility.
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.
In this C implementation, we utilize recursive backtracking to explore all possible subsets of the input array. We use a helper function named 'backtrack' which constructs subsets by either including or excluding each element as we proceed through the array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n * n), where n is the length of nums. We have 2^n subsets, and copying each subset takes O(n).
Space Complexity: O(n), where n is the depth of the recursion stack.
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:
This C solution employs bit manipulation. Each subset is represented by a binary counter, where bitwise operations discern element inclusion based on integer value masks at each positional value.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n * n), mapping to subset enumeration.
Space Complexity: O(1), as it utilizes constants.
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(2^n * n), where n is the length of nums. We have 2^n subsets, and copying each subset takes O(n). |
| Bit Manipulation | Time Complexity: O(2^n * n), mapping to subset enumeration. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(n * 2^n) | O(n) recursion stack | Best for interviews and when learning subset generation patterns |
| Bit Manipulation | O(n * 2^n) | O(1) auxiliary | Useful when you want an iterative solution or are comfortable with bitmask enumeration |
Subsets - Backtracking - Leetcode 78 • NeetCode • 341,241 views views
Watch 9 more video solutions →Practice Subsets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor