Problem Statement
Given an integer array nums of unique elements, return all possible subsets (the power set).
- Note: The solution set must not contain duplicate subsets. Return the solution in any order.
Example Inputs
Example 1:
Problem Solution
Approach
To generate all possible subsets of the given array, we can use a recursive backtracking approach. The idea is to explore all possibilities by deciding for each element whether to include it in the current subset or not.
Steps
- Initialize: Start with an empty subset and begin processing from the first element.
- Decision Point: For each element in the array, decide to either:
- Include the current element in the subset.
- Exclude the current element from the subset.
- Recursion: Recursively apply the above decision to the next element until all elements have been processed.
- Store Subset: Once all decisions have been made for a subset, add it to the list of possible subsets.
- Backtrack: Remove the last element added and explore other possibilities.
Time & Space Complexity
- Time Complexity: O(2^n), where n is the number of elements in
nums. Each element has two choices: include or exclude.
- Space Complexity: O(n), which is the space required for the recursion stack and the space for storing subsets.
Code Snippet
Dry Run
Let's perform a dry run with nums = [1, 2].
- Initial Call:
rec(0, [], [1, 2])
- Level 0:
- Include 1:
output = [1]
- Level 1:
- Include 2:
output = [1, 2]
- Level 2: Add
[1, 2] to ans.
- Exclude 2:
output = [1]
- Exclude 1:
output = []
- Level 1:
- Include 2:
output = [2]
- Exclude 2:
output = []
Final Subsets: [ [1, 2], [1], [2], [] ]
Complexity Analysis
Optimized Time and Space
The recursive backtracking approach ensures that all possible subsets are explored efficiently. Although the number of subsets grows exponentially with the size of nums, this method systematically explores each possibility without redundant computations.
- Optimized Time Complexity: O(2^n)
- Optimized Space Complexity: O(n) for the recursion stack and temporary storage.
Conclusion
Generating all subsets of a given set is a fundamental problem that showcases the power of recursive backtracking. By making a binary choice at each step (include or exclude), we can efficiently explore all possible combinations. Understanding this approach not only helps in solving similar combinatorial problems but also strengthens problem-solving skills in recursive thinking and algorithm design.