Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets, and the order of subsets does not matter.

Example:

Input: nums = [1,2,3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

---

Intuition

We are asked to generate all possible combinations of elements from the array — that is, the power set.

If the array has n elements, the total number of subsets = 2ⁿ.

Each element has two choices:

• It can be included in the subset, or
• It can be excluded.

This forms a decision tree, and we can use either:

• Backtracking (recursive depth-first search), or
• Bit manipulation (iterative, using binary representation).

---

Approach 1: Backtracking (Recursive DFS)

Key idea:
Use recursion to explore all inclusion/exclusion possibilities for each element.

Steps:

1. Start with an empty list (current subset).
2. At each index:
   • Include the element and recurse.
   • Exclude the element and recurse.
3. When you reach the end of the array, add the subset to the result.

---

Java Solution (Backtracking)

import java.util.*;

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, nums, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int start, int[] nums, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);               // include
            backtrack(i + 1, nums, current, result);
            current.remove(current.size() - 1); // backtrack
        }
    }
}

---

Complexity Analysis

• Time Complexity: O(2ⁿ × n)
  Each of the 2ⁿ subsets may take O(n) time to copy into the result list.
• Space Complexity: O(n) (recursion depth + temporary subset list)

---

Dry Run

Input: [1, 2, 3]

Let’s walk through the recursion:

Step	Current Subset	Action	Result So Far
Start	[]	Add []	[[]]
Include 1	[1]	Add [1]	[[], [1]]
Include 2	[1,2]	Add [1,2]	[[], [1], [1,2]]
Include 3	[1,2,3]	Add [1,2,3]	[[], [1], [1,2], [1,2,3]]
Backtrack → Remove 3	[1,2]	—	—
Backtrack → Remove 2	[1]	Include 3	[[], [1], [1,2], [1,2,3], [1,3]]
Backtrack → Remove 1	[]	Include 2	[[], [1], [1,2], [1,2,3], [1,3], [2]]
Include 3	[2,3]	Add [2,3]	[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3]]
Backtrack → Remove 2	[]	Include 3	[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Final Output:

[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

---

Approach 2: Bit Manipulation (Iterative)

Each subset corresponds to a bitmask of length n:

• Bit 1 → include that element.
• Bit 0 → exclude that element.

For example, if nums = [1, 2, 3]:

Binary mask → Subset
000 → []
001 → [3]
010 → [2]
011 → [2,3]
100 → [1]
101 → [1,3]
110 → [1,2]
111 → [1,2,3]

Code:

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    int total = 1 << n; // 2^n

    for (int mask = 0; mask < total; mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(nums[i]);
            }
        }
        result.add(subset);
    }

    return result;
}

---

Key Insights

1. The backtracking solution is intuitive and easy to extend for constraints (like subset sums or conditions).
2. The bitmask approach is faster and more concise but harder to modify.
3. Both generate the power set of nums efficiently.