Backtracking: Decision Tree & Constraints Visualizer & Step-by-Step Algorithm Solution

Explore the universal backtracking template: watch the state space tree expand, witness constraint pruning terminate invalid branches early, and trace how choices are systematically undone.

Category: backtracking | Difficulty: Medium

Tags: Backtracking, Decision Tree, Pruning, Recursion, Combinations, State Space

Backtracking: Decision Tree & Constraints

∅
100%
state
current[]
currentSum0
maxSum3
targetLength2
results[]
resultsCount0
start0
Initialization
1/45
Explanation

Starting backtracking with choices = [1, 2, 3]. Target length = 2, max sum constraint ≤ 3. State space tree begins at empty root ∅.

Source Code
1function backtrack(start: number, current: number[]): void {
2 if (current.length === targetLength) {
3 results.push([...current]); // Found valid solution
4 return;
5 }
6
7 for (let i = start; i < choices.length; i++) {
8 const choice = choices[i];
9 if (violatesConstraints(current, choice)) {
10 continue; // Prune invalid branch
11 }
12
13 current.push(choice); // 1. Choose
14 backtrack(i + 1, current); // 2. Explore
15 current.pop(); // 3. Unchoose (Backtrack)
16 }
17}