Backtracking Concept and Decision Tree Visualization in DSA Typescript - Build from Scratch

Backtracking Concept and Decision Tree Visualization

📖 Scenario: Imagine you are helping a friend solve a simple puzzle where they must choose numbers from a list to reach a target sum. You will use backtracking to explore all possible choices step-by-step and visualize the decision tree of choices made.

🎯 Goal: Build a TypeScript program that uses backtracking to find all combinations of numbers that sum up to a target. Visualize the decision tree by printing the current path at each step.

📋 What You'll Learn

Create an array of numbers called candidates with values [2, 3, 6, 7]

Create a variable called target with value 7

Write a backtracking function called backtrack that tries adding numbers to a current path to reach the target sum

Print each valid combination found as a path

Print the current path at each decision step to visualize the decision tree

💡 Why This Matters

🌍 Real World

Backtracking is used in puzzles, games, and solving problems like finding combinations or permutations where you explore choices step-by-step.

💼 Career

Understanding backtracking helps in algorithm design, coding interviews, and solving complex problems in software development.

1

Create the initial data setup

Create an array called candidates with values [2, 3, 6, 7] and a variable called target with value 7.

DSA Typescript

// Your code here

Hint

Use const candidates: number[] = [2, 3, 6, 7]; and const target: number = 7;

2

Add a variable to hold the current path

Create an empty array of numbers called currentPath to store the current combination of numbers during backtracking.

DSA Typescript

const candidates: number[] = [2, 3, 6, 7];
const target: number = 7;
// Your code here

Hint

Use const currentPath: number[] = []; to hold the current numbers chosen.

3

Write the backtracking function

Write a function called backtrack that takes two parameters: start (number) and remainingTarget (number). Inside, if remainingTarget is 0, print the currentPath. Otherwise, loop over candidates starting from start, add the candidate to currentPath, print the current path to visualize the decision tree, recursively call backtrack with updated parameters, then remove the last number from currentPath to backtrack.

DSA Typescript

const candidates: number[] = [2, 3, 6, 7];
const target: number = 7;
const currentPath: number[] = [];
// Your code here

Hint

Use recursion with base case remainingTarget === 0. Print currentPath at each step to show the decision tree.

4

Call the backtracking function and print results

Call the backtrack function with start as 0 and remainingTarget as target to start the search.

DSA Typescript

const candidates: number[] = [2, 3, 6, 7];
const target: number = 7;
const currentPath: number[] = [];

function backtrack(start: number, remainingTarget: number): void {
    if (remainingTarget === 0) {
        console.log('Found combination:', currentPath.join(' -> '));
        return;
    }
    for (let i = start; i  remainingTarget) continue;
        currentPath.push(candidates[i]);
        console.log('Current path:', currentPath.join(' -> '));
        backtrack(i, remainingTarget - candidates[i]);
        currentPath.pop();
    }
}
// Your code here

Hint

Call backtrack(0, target); to start the search and print all paths.