Generate every subset of a set. For each element there are exactly two choices, take it or leave it, so the whole search is a binary decision tree with 2ⁿ leaves.
Walk the elements left to right. At index i, branch two ways: include nums[i] in the path, or skip it. Recurse to i+1 each way.
When you run past the last index, the path is one complete subset, record it.
{} and the full setvoid dfs(int i, vector<int>& nums,
vector<int>& path, vector<vector<int>>& out) {
if (i == nums.size()) { // leaf: one complete subset
out.push_back(path);
return;
}
// choice 1: include nums[i]
path.push_back(nums[i]);
dfs(i + 1, nums, path, out);
path.pop_back(); // backtrack
// choice 2: exclude nums[i]
dfs(i + 1, nums, path, out);
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> out;
vector<int> path;
dfs(0, nums, path, out);
return out; // 2^n subsets
}2ⁿ subsets, each up to length n to copy into the output.
Recursion depth and the working path, output excluded.
The count of subsets, from empty set to the full set.
nums[i]==nums[i-1] on the exclude branch to avoid repeat subsets.