the state-space tree
When you build a solution by a sequence of choices, you can draw a picture of all the ways those choices could go. Start with a node for having decided nothing. From it, draw one branch for each option of the first decision; from each of those, branches for the second decision; and so on. The result is the state-space tree: the root is the empty partial solution, every edge is one decision, every node is a partial solution, and every leaf is a complete candidate.
This tree is the search space made visible as a structure you can walk. A node at depth d represents a partial solution where the first d decisions are fixed. The path from the root to a leaf spells out a full set of choices — one complete candidate. The number of leaves is the size of the search space: branch 2 ways at each of n items and you get a tree with 2^n leaves (subsets); branch on which element comes next and you get n! leaves (permutations). Backtracking is exactly depth-first traversal of this tree, and the make-recurse-undo motion corresponds to going down an edge, exploring the subtree, and coming back up.
Drawing the state-space tree is what turns a vague brute force into a method you can reason about and speed up. Pruning means cutting off a subtree at an internal node — declaring this partial solution cannot lead to any valid (or any optimal) leaf, so skip everything below it. Feasibility pruning cuts subtrees that violate a constraint; bounding (branch and bound) cuts subtrees whose best possible leaf is worse than a solution already found. The whole art of exhaustive search is to do a DFS of this tree while visiting as few nodes as the constraints allow.
For subsets of {a, b, c}, the state-space tree branches take-or-skip at a (depth 1), then b (depth 2), then c (depth 3). Its 2^3 = 8 leaves are the 8 subsets. If a constraint says you may take at most one item, the node 'took a and b' is infeasible — prune it, and the whole subtree of further choices below it never gets visited.
Root = decided nothing; leaf = decided everything; pruning lops off a whole subtree at one infeasible node.
The state-space tree is a conceptual map, not something you build in memory all at once — DFS visits it node by node using only the path from root to the current node, so the space cost is the tree's depth, not its (exponential) number of nodes.