Backtracking vs Branch & Bound

Aspect	Backtracking	Branch & Bound (B&B)
Search	DFS over state-space tree; builds solution incrementally, backtracks on dead end.	BFS / best-first over state-space; uses bounds to prune non-promising branches.
Pruning	Constraint-based: discard if violates explicit / implicit constraints (e.g., queen attacks, edge missing).	Bound-based: compute lower bound (min) / upper bound (max) for subtree; prune if bound worse than current best. Requires bounding function.
Solution	Finds all or first feasible; works for decision / enumeration (N-Queens, Hamiltonian).	Finds optimal solution; for optimization (TSP, Knapsack, Job Assignment).
Data structure	Stack (recursion).	Queue / Priority queue (live nodes list), often with heap ordered by bound.
Types	No cost; just feasibility.	Three variants: FIFO B&B, LIFO B&B, LC (Least Cost) / A* B&B using priority.
Time	Worst $O(b^d)$ branching.	Also exponential worst, but bounds often cut huge portions.
Examples	N-Queens, Sudoku, Subset Sum decision, Graph Coloring.	TSP B&B (Held-Karp lower bound), 0/1 Knapsack (fractional knapsack upper bound), 15-puzzle.
Guarantee	Complete if search exhaustive.	Complete + optimal when bounds are admissible (never overestimate for max).

Combined: Many algorithms blend both — e.g., backtracking with bounding (branch-and-bound depth-first) like recursive Knapsack with upper bound.