Backtracking

Explore all possibilities recursively, pruning invalid branches early.

10 problems 0 Easy 9 Medium 1 Hard

Overview

Backtracking is systematic brute force with pruning. It explores all candidates but abandons a path as soon as it determines the path cannot lead to a valid solution.

When to Use

Generate all permutations/combinations/subsets
N-Queens
Sudoku solver
Word search
Letter combinations of phone number

Common Mistakes

Forgetting to undo the choice (backtrack) after recursion
Not pruning early — missing the constraint check
Modifying the input array without restoring it

Complexity

Time

Exponential — O(n!) or O(2ⁿ) depending on problem

Space

O(n) call stack depth

function backtrack(result, current, start, nums) {
  result.push([...current]); // record current state

  for (let i = start; i < nums.length; i++) {
    // Prune: skip duplicates
    if (i > start && nums[i] === nums[i-1]) continue;

    current.push(nums[i]);           // choose
    backtrack(result, current, i + 1, nums); // explore
    current.pop();                   // un-choose
  }
}

Problems (10)

Hide completed

Problem	Difficulty	Companies	Freq
Permutations	Medium	LinkedInMicrosoft +1	High
Subsets	Medium	FacebookAmazon +1	High
Combination Sum	Medium	AmazonFacebook +1	High
Word Search	Medium	AmazonFacebook +2	High
Letter Combinations of a Phone Number	Medium	AmazonFacebook +3	High
Generate Parentheses	Medium	AmazonGoogle +2	High
N-Queens	Hard	AmazonMicrosoft	Medium
Palindrome Partitioning	Medium	AmazonFacebook +1	Medium
Combination Sum II	Medium	AmazonAdobe	Medium
Subsets II	Medium	FacebookAmazon	Medium

Backtracking is just DFS with pruning. Once you see that, permutations, combinations, subsets, and N…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee

Buy me a coffee