Subsets

medium backtracking power set

Problem

Given an array of distinct integers, return all possible subsets (the power set). The output must contain each subset exactly once and may be 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;
}

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