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 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.
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.
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.
Time Complexity: O(2^n * n), mapping to subset enumeration.
Space Complexity: O(1), as it utilizes constants.
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:
i = n, it means the current search has ended. Add the current subset t to the answer array ans, and then return.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.
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.
| 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. |
| DFS (Backtracking) | — |
| Binary Enumeration | — |
| 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 |
Subsets - Backtracking - Leetcode 78 • NeetCode • 430,960 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