Subsets

medium backtracking power set

Problem

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.

Inputnums = [1, 2, 3]

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

For each index, branch on include vs. exclude — collect the running subset at every recursion entry.

nums (distinct, comma-separated)

def subsets(nums):
    out = []
    cur = []
    def go(i):
        out.append(cur.copy())
        for j in range(i, len(nums)):
            cur.append(nums[j])
            go(j + 1)
            cur.pop()
    go(0)
    return out

function subsets(nums) {
  const out = [];
  const cur = [];
  function go(i) {
    out.push(cur.slice());
    for (let j = i; j < nums.length; j++) {
      cur.push(nums[j]);
      go(j + 1);
      cur.pop();
    }
  }
  go(0);
  return out;
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        go(nums, 0, cur, out);
        return out;
    }
    void go(int[] nums, int i, List<Integer> cur, List<List<Integer>> out) {
        out.add(new ArrayList<>(cur));
        for (int j = i; j < nums.length; j++) {
            cur.add(nums[j]);
            go(nums, j + 1, cur, out);
            cur.remove(cur.size() - 1);
        }
    }
}

void go(vector<int>& nums, int i, vector<int>& cur, vector<vector<int>>& out) {
    out.push_back(cur);
    for (int j = i; j < (int)nums.size(); j++) {
        cur.push_back(nums[j]);
        go(nums, j + 1, cur, out);
        cur.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> out;
    vector<int> cur;
    go(nums, 0, cur, out);
    return out;
}

Explanation

We want the power set — every possible subset of the array, from the empty set up to the whole array. This solution grows subsets with backtracking.

The function go(i) records the current subset cur the moment it is called. That single line out.append(cur.copy()) is what captures the empty set and every partial subset along the way — there is no separate "finish" condition.

Then it loops j from i to the end. For each j it includes nums[j], recurses with go(j + 1) to extend the subset using only later elements, and then removes it to back up and try the next element.

Starting each recursion at j + 1 is the key: it guarantees elements are only ever added in increasing index order, so no subset is generated twice and no arrangement is repeated.

Example: nums = [1, 2, 3]. We collect [], then [1], [1,2], [1,2,3], [1,3], then [2], [2,3], and finally [3] — all 2³ = 8 subsets.

Time: O(n · 2ⁿ) Space: O(n) (excluding output)