Every backtracking problem is a walk down a decision tree: choose an option, explore deeper, then un-choose to try the next. Pruning kills dead branches early. Here it's subsets, cut whenever the running sum blows past a target.
At each node you make a choice (add an element to the path), recurse to explore what follows, then undo the choice before trying the next option. That undo is the "backtrack".
The recursion tree is the search space. Every root-to-leaf path is one candidate.
// generic backtracking skeleton (here: subsets with a prune)
void backtrack(int i, vector<int>& nums, int sum, int target,
vector<int>& path, vector<vector<int>>& out) {
if (sum > target) return; // PRUNE: dead branch
if (i == nums.size()) { // leaf: a complete candidate
out.push_back(path);
return;
}
// choice 1: include nums[i]
path.push_back(nums[i]); // CHOOSE
backtrack(i + 1, nums, sum + nums[i], target, path, out); // EXPLORE
path.pop_back(); // UNCHOOSE (backtrack)
// choice 2: skip nums[i]
backtrack(i + 1, nums, sum, target, path, out);
}Up to 2ⁿ leaves, each copying an O(n) path. Pruning cuts this in practice.
Recursion depth and the path, ignoring the output list itself.
Branching factor × depth defines the search space you traverse.