1. Problem Statement (Simple Explanation)
You’re given an integer array nums where all elements are unique.
You must return all possible subsets (the power set) of nums.
A subset can be of any size: from 0 elements (the empty set []) up to all elements (nums itself).
The resulting list must not have duplicate subsets.
You can return subsets in any order.
2. Examples
Example 1:
Input: nums = [1,2,3]
All subsets:
[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Subsets:
[]
[0]
Output: [[],[0]]
3. Approach – Backtracking (DFS / Recursion)
We want all subsets = all combinations of choosing or not choosing each element.
We can think of it as:
For each element nums[i], we have two choices:
Include it in the current subset.
Exclude it.
Recurse over index i from 0 to n-1, and whenever we reach i == n, we add the current subset to the result.
Alternatively, we can build subsets incrementally:
Maintain:
current list for the current subset.
start index for where to continue picking next elements.
At each recursion step:
Add the current subset to the result (since any prefix is a valid subset).
Then, for each i from start to n-1:
Add nums[i] to current.
Recurse with start = i + 1.
Backtrack (remove nums[i] from current).
This enumerates all subsets without duplicates (because nums has unique elements and we never go backwards).
Pseudo-code:
Let n = len(nums).
Number of subsets = 2n.
Each subset copy costs O(k) where k is subset size, but total is O(n * 2n).
So:
Time: O(n * 2n)
Space:
O(n) recursion depth + O(n) for current.
Result uses O(n * 2n) (required).
n <= 10 → 2n <= 1024, easily manageable.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
9. Alternative Approach – Bitmask Enumeration
For completeness (good for teaching):
There are 2n subsets.
We can represent decisions (include/exclude) with n-bit integers from 0 to 2n - 1.
For each integer mask, build a subset:
For bit i from 0 to n-1:
If mask & (1 << i) is non-zero → include nums[i].
This is another O(n·2n) approach, iterative instead of recursive.
Comments
Post a Comment