HTML5ANDCSS3Tools and Tutorials

HTML5ANDCSS3Tools and Tutorials

Backtracking Explained — DSA Tutorial - HTML5ANDCSS3

Backtracking

Backtracking Explained

Written by Swapnil RajaPublished 28 Aug 2026

Backtracking is brute force with an eraser. You try a choice, follow it, and if it leads nowhere you undo it and try the next - which is why the undo step is the part that matters.

The template

Every backtracking solution is this shape:

Choose, explore, unchoose

javascript

// A runnable instance of the template: every 2-element combination.
function backtrack(current, options, results, start) {
  if (current.length === 2) {          // a complete solution
    results.push([...current])         // copy — current keeps changing
    return
  }

  for (let i = start; i < options.length; i++) {
    current.push(options[i])                       // choose
    backtrack(current, options, results, i + 1)    // explore
    current.pop()                                  // unchoose
  }
}

const results = []
backtrack([], ["a", "b", "c"], results, 0)
console.log(results)   // [["a","b"], ["a","c"], ["b","c"]]

PreviousTurning Recursion Into Iteration NextClassic Backtracking Problems

Every subset

javascript

function subsets(nums) {
  const results = []

  function build(start, current) {
    // Every state is itself a valid subset.
    results.push([...current])

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i])
      build(i + 1, current)   // i + 1, so no element repeats
      current.pop()
    }
  }

  build(0, [])
  return results
}

console.log(subsets([1, 2, 3]))
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Every ordering

javascript

function permutations(nums) {
  const results = []
  const used = new Array(nums.length).fill(false)

  function build(current) {
    if (current.length === nums.length) {
      results.push([...current])
      return
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue

      used[i] = true
      current.push(nums[i])

      build(current)

      current.pop()      // undo both
      used[i] = false
    }
  }

  build([])
  return results
}

console.log(permutations([1, 2, 3]).length)  // 6

Combinations summing to a target

javascript

function combinationSum(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b)
  const results = []

  function build(start, current, remaining) {
    if (remaining === 0) {
      results.push([...current])
      return
    }

    for (let i = start; i < sorted.length; i++) {
      // Sorted, so every later candidate is bigger too — stop entirely.
      if (sorted[i] > remaining) break

      current.push(sorted[i])
      build(i, current, remaining - sorted[i])   // i, so reuse is allowed
      current.pop()
    }
  }

  build(0, [], target)
  return results
}

console.log(combinationSum([2, 3, 6, 7], 7))  // [[2,2,3], [7]]