Crack the Backend

Problem Statement

Given an integer array nums with unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the result in any order.

A subset can be any set of indices; we can represent each subset by the list of chosen elements. The empty set [] is a valid subset.
Since elements are unique, we get 2^n subsets. We can generate them by, at each index, either including or excluding the element (backtracking).

Key Observations

At each position start, we have two choices: include nums[start] in the current subset or exclude it. We recurse on start+1 for both choices. Whenever we have processed all elements (start == n), the current path is a complete subset — add a copy to the result.
Alternatively: for start from 0 to n-1, we add nums[start] to the path, recurse on start+1 (all subsets that include nums[start]), then remove it and recurse (subsets that exclude nums[start]). We also add the current path at every step (so we record subsets of all sizes).
Implementation: add the current path to result at the beginning of each recursive call (or when we reach the end); then for each i >= start, add nums[i], recurse i+1, remove.

Approach

High-level: Backtrack: at each step, the current path is a subset — add it to the result. Then for each remaining index i, include nums[i], recurse on i+1, then remove nums[i] (exclude).

Steps:

result = new ArrayList<>(), path = new ArrayList<>(). Call dfs(nums, 0, path, result).
In dfs(start): add a copy of path to result. For i = start..n-1: path.add(nums[i]), dfs(i+1), path.remove(path.size()-1).
Return result.

Implementation

Java

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

void dfs(int[] nums, int i, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));

    for (int j = i; j < nums.length; j++) {
        path.add(nums[j]);
        dfs(nums, j + 1, path, result);
        path.remove(path.size() - 1);
    }
}

Test Cases

Example 1

Input

nums = [1,2,3]

Expected

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

Explanation

All 2^3 subsets.

Complexity Analysis

Time: O(n * 2^n).
Space: O(n).

Follow-ups

Subsets II: array may have duplicates; avoid duplicate subsets.