Subsets

MediumBacktracking

Return all possible subsets (the power set) of an array of distinct integers, in any order.

Constraints

1 <= nums.length <= 10
All numbers are unique

Backtracking include/exclude

Time O(n * 2^n)Space O(n) recursion depth

Walk the array choosing, at each index, to include or skip the element. Record the current subset at every node of the decision tree.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur;
    function<void(int)> bt = [&](int i) {
        if (i == (int)nums.size()) { res.push_back(cur); return; }
        cur.push_back(nums[i]); bt(i + 1); cur.pop_back();
        bt(i + 1);
    };
    bt(0);
    return res;
}