Subsets

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]]

Example 2:

Input: nums = [0] Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Approach: Backtracking (Include/Exclude Each Element)

Algorithm

1. Use a recursive function that, at each index, either includes or excludes the current element
2. At every call, add a copy of the current subset to the result
3. Recursively continue from the next index
4. After recursion, backtrack by removing the last added element

Time & Space Complexity

• Time Complexity: O(2^n) - there are 2^n subsets
• Space Complexity: O(n) - recursion depth (excluding the output)

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class Subsets {

    /**
     * Return all possible subsets (the power set).
     * @param nums Array of unique elements
     * @return List of all subsets
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

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

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

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        System.out.println("Input: nums = [1,2,3]");
        System.out.println("Output: " + subsets(nums1));
        // Expected: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

        int[] nums2 = {0};
        System.out.println("Input: nums = [0]");
        System.out.println("Output: " + subsets(nums2));
        // Expected: [[], [0]]
    }
}

Alternative Approach: Iterative (Build Subsets Incrementally)

Start with the empty subset, and for each element, append it to every existing subset.

import java.util.ArrayList;
import java.util.List;

public class SubsetsIterative {

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        for (int num : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> subset = new ArrayList<>(result.get(i));
                subset.add(num);
                result.add(subset);
            }
        }

        return result;
    }
}

Key Points

1. Power Set Size: 2^n subsets for an array of n distinct elements
2. No Duplicates: Because elements are unique and each element is considered exactly once
3. Any Order Allowed: The result order does not matter
4. Start Index: Passing i + 1 ensures each element is only used once in a subset
5. Iterative Option: The incremental build approach gives the same result without recursion