Subsets

Share

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]]
Explanation: All 2^3 = 8 subsets of [1,2,3] are listed.
Example 2
Input: nums = [0]
Output: [[],[0]]
Explanation: Two subsets exist: the empty set and [0].

Solution Approach

We use a classic backtracking approach where for each element we make a binary choice: either include it in the current subset or skip it. We maintain a running list and add it to the result at every recursive call (not just at leaves).

  • Start with an empty current subset and call the recursive helper with index 0.
  • At each call, add a copy of the current subset to the result list.
  • Iterate from the current index to the end of the array, add nums[i], recurse with i+1, then remove the last element (backtrack).
  • Because we always advance the start index, no element is reused and no subset is generated twice.
Java
import java.util.*;

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

    private void backtrack(int[] nums, int start,
                           List<Integer> current,
                           List<List<Integer>> result) {
        // Add snapshot of current subset at every node
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);          // choose
            backtrack(nums, i + 1, current, result); // explore
            current.remove(current.size() - 1);      // un-choose
        }
    }
}
Complexity Analysis:

Time complexity: O(n * 2^n). There are 2^n subsets and copying each takes O(n) in the worst case.
Space complexity: O(n) recursion stack depth, plus O(n * 2^n) for the output.