Given an array numsArray of unique integers of unique integers, return all possible subsets (the power set). The solution set must not contain duplicate subsets. You may return the solution in any order.
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, abandoning solutions ("backtracking") as soon as it determines that the solution cannot be valid.
Each level represents a decision point for one element. Left branch = include, Right branch = exclude.
[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]
When you need to generate all possible combinations or arrangements of elements.
When each element has a binary choice (take it or leave it).
When you need to explore all possible states or configurations.
def subsets(self, array_nums): output_list = [] current_subset = []
Create a result list to store all subsets and a temporary list to build the current subset.
def explore(position): # Base case: reached end of array if position >= len(array_nums): output_list.append(current_subset.copy()) return
Check if we've processed all elements. If yes, add a copy of the current subset to results.
# Choice 1: Include current element current_subset.append(array_nums[position]) explore(position + 1) current_subset.pop() # Backtrack!
Add the element, explore this branch, then remove it (backtrack) to explore the other branch.
# Choice 2: Exclude current element explore(position + 1)
Simply move to the next index without adding the current element.
explore(0) return output_list
Kick off the recursion from index 0 and return all collected subsets.
class Solution: def subsets(self, array_nums): output_list = [] current_subset = [] def explore(position): if position >= len(array_nums): output_list.append(current_subset.copy()) return # Include current element current_subset.append(array_nums[position]) explore(position + 1) current_subset.pop() # Exclude current element explore(position + 1) explore(0) return output_list
Enter an array and click Start to visualize
Modify the code below and click "Run" to see the results. Try different approaches!
Add a parameter k and only include subsets with exactly k elements.
Rewrite the solution without recursion using iteration.
Can you optimize with caching? (Hint: this problem doesn't benefit from memoization, but understanding why is valuable!)
Build subsets iteratively by adding each element to all existing subsets.
def subsets(self, array_nums): output_list = [[]] for element in array_nums: current_size = len(output_list) for idx in range(current_size): new_subset = output_list[idx] + [element] output_list.append(new_subset) return output_list
Use binary representation where each bit indicates whether to include an element.
def subsets(self, array_nums): array_length = len(array_nums) output_list = [] for mask in range(1 << array_length): current_subset = [] for idx in range(array_length): if mask & (1 << idx): current_subset.append(array_nums[idx]) output_list.append(current_subset) return output_list
| Approach | Pros | Cons |
|---|---|---|
| Backtracking | Intuitive, easy to understand decision tree | Uses call stack space O(n) |
| Iterative | No recursion, constant extra space | Less intuitive logic |
| Bit Manipulation | Elegant, mathematical approach | Limited to small arrays (n ā¤ 30) |
# This will fail! output_list.append(current_subset)
# Must copy the list output_list.append(current_subset.copy())
if position == len(array_nums) - 1:
if position >= len(array_nums):
current_subset.append(array_nums[position]) explore(position + 1) # Missing pop()!
current_subset.append(array_nums[position]) explore(position + 1) current_subset.pop() # Essential!
# Will cause duplicates explore(position)
# Move to next element explore(position + 1)
Click each card to flip and test your knowledge
When the index reaches or exceeds the array length (position >= len(array_nums)), we've processed all elements and add the current subset to results.
We generate 2āæ subsets (each element has 2 choices), and copying each subset into the result takes O(n) time in the worst case.
Undoing a choice (removing an element from the current subset) after exploring one path, so we can explore alternative paths in the decision tree.
def backtrack_subsets(array_nums): output_list = [] current_subset = [] def explore(start_pos): # Base case if start_pos >= len(array_nums): output_list.append(current_subset.copy()) return # Include current element current_subset.append(array_nums[start_pos]) explore(start_pos + 1) current_subset.pop() # Exclude current element explore(start_pos + 1) explore(0) return output_list
Now that you've mastered Subsets, try these related problems: