Perfect. I’ll create a comprehensive guide on Backtracking that progresses from beginner to advanced using a pattern-based approach. I’ll break it down into key backtracking patterns—like permutations, combinations, subsets, decision trees, constraint satisfaction, and optimized pruning techniques.

Each pattern will include:

• A detailed explanation

• Common problem types

• Decision-making breakdown

• Practical tips

• Flowchart-based visual aids

• 10 curated problems per pattern (with full JS code and explanation for the most important ones)

This will be ideal for mastering backtracking in both coding interviews and competitive programming. I’ll get started and update you once the guide is ready!

Backtracking Patterns: A Comprehensive Guide from Beginner to Advanced

Backtracking is a powerful algorithmic technique used to solve problems by exploring all potential solutions and backtracking (undoing steps) when a path fails to satisfy constraints. Think of it like navigating a maze: you make choices to move forward, and if you hit a dead end, you backtrack to the last decision point and try a different route (Backtracking Demystified: The Algorithm Pattern That Powers Problem Solving - TeddySmith.IO). This depth-first search of a decision tree systematically builds candidates for solutions and abandons those that violate the problem’s rules (Backtracking Demystified: The Algorithm Pattern That Powers Problem Solving - TeddySmith.IO). Backtracking is especially effective for problems involving combinatorial search – such as generating subsets, permutations, combinations – and for constraint satisfaction problems like puzzles and games (Backtracking Demystified: The Algorithm Pattern That Powers Problem Solving - TeddySmith.IO).

In this guide, we will progressively explore a set of backtracking patterns from beginner to advanced levels. Each pattern represents a common problem structure and a typical backtracking approach to solve it. By mastering these patterns, you’ll gain a toolbox for tackling a wide range of coding interview and competitive programming challenges. We will cover the following patterns:

• Subsets Pattern: Include-or-exclude decisions (power set generation and related problems).

• Combinations Pattern: Choosing k elements or meeting specific selection criteria (combinatorial combinations, sum-based selections).

• Permutations Pattern: Generating all arrangements or orderings of elements.

• Decision Tree Pattern: Multi-step decision problems (paths, sequences, partitions) that don’t fit neatly into simple subsets/permutations.

• Constraint Satisfaction Pattern: Problems with complex constraints (like puzzles – N-Queens, Sudoku) requiring pruning of invalid states.

• Pruning Techniques: General strategies to cut off branches early and optimize backtracking.

For each pattern, we’ll provide a detailed explanation of how it works, the types of problems it solves, a breakdown of the decision-making logic, and tips and tricks. We’ll also use visual aids (like recursion trees or analogies) to illustrate the backtracking process. Finally, each section includes a list of 10 practice problems (with a mix of easy, medium, and hard difficulties) and a few fully worked-out examples in JavaScript with clear explanations. These examples follow modern JS best practices and are heavily commented to help you understand the backtracking logic step by step.

Let’s dive in and explore each pattern in depth.

Pattern 1: Subsets (Include-Exclude Pattern)

The Subsets pattern is one of the most fundamental backtracking approaches. It involves making binary decisions for each element – either include the element in the current subset or exclude it – exploring all possible combinations of included elements. This naturally generates the power set (the set of all subsets) of a given set. The recursion forms a binary tree of decisions, where each level considers one element and branches into two choices (with or without that element).

How the Subsets Pattern Works

At its core, the subsets pattern treats every element as a choice point:

• We iterate through elements (or positions) one by one.

• At each element, we have two possibilities: take it or leave it.

• We recursively explore both possibilities, building up partial subsets along the way.

• Every time we reach the end (considered all elements), we have a complete subset to record.

Because each element has two states (in or out), an input of size n yields 2^n possible subsets. Backtracking systematically enumerates these by depth-first traversal of the implicit decision tree. It’s essentially a DFS on a binary recursion tree until all elements are processed.

Common problem structures: Generating all subsets of a set (power set), generating all subsequences of a string, toggling each character’s state (e.g. letter case permutations), or any scenario where each of a series of items can be either selected or not. These problems often ask for “all combinations” without regard to order.

Decision-making logic: We typically use recursion with an index to track our position in the input:

• If the index is at the end of the input, we record the current subset (base case).

• Otherwise, decide to include the current element (add it to the current subset and recurse to next index), then backtrack (remove it), and decide to exclude the current element (just recurse to next index without it).

• This “include then exclude” (or vice versa) pattern ensures all subsets are explored.

Key insights and tips:

• Use a recursive helper that carries the current index and the current subset (or path). Each recursive call advances the index.

• Ensure to clone or copy the subset when recording a result (to avoid aliasing issues in recursion).

• If the input set has duplicates, sort it first and use a check to skip generating subsets that would be duplicates (for example, when excluding a value, skip subsequent recursive calls on the same value to avoid duplicate subset outcomes).

• This pattern naturally handles subsets of all sizes. If you only need subsets of a specific size k, you can add a condition to record subsets only when they reach length k.

• Time complexity is O(2^n) for generating all subsets (exponential in input size), which is expected because there are 2^n subsets. Pruning or special techniques (like iterative bitmask generation) can generate subsets more succinctly, but the complexity of listing them all remains exponential.

Visual illustration: The recursion tree below shows how subsets of a set are generated. Each level corresponds to deciding on the next element (with = include it, without = exclude it). This example shows the subsets of {a, b, c, d}being built. The green branches indicate including an element and the red branches indicate excluding it. Following all branches yields every subset from ∅ (no elements) up to {a, b, c, d}.

(Zunayed Ali) Recursion tree illustrating subset generation by choosing or skipping each element. Green (“with”) branches include the element, and red (“without”) branches exclude it, eventually listing all subsets (Zunayed Ali).

Example Problems for Subsets Pattern

The following table lists 10 practice problems that rely on the subsets (include-exclude) backtracking pattern, covering a range of difficulties:

Some of these problems could also be categorized under combinations, but they can be approached with a simple include/exclude mindset. The include-exclude pattern is a foundational approach that often overlaps with the combination pattern when a target sum or size is involved.

Solved Example: Generating All Subsets (Power Set)

Let’s start with a straightforward example – generating all subsets of a given set of distinct numbers. This corresponds to LeetCode 78 – Subsets. We’ll use backtracking to build subsets by including or excluding each number in turn.

Problem: Given an array of distinct integers nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Approach: We will use a recursive backtracking function that takes an index and the current subset (path) built so far. At each index, we have two choices: take the element or skip it. We explore both, and when we reach beyond the last index, we record the subset. We do not need to worry about duplicates here since nums has distinct integers. The recursion tree will branch 2 ways at each element.

/**
 * Returns all subsets of the given array.
 * @param {number[]} nums - Array of distinct integers.
 * @return {number[][]} All possible subsets of nums.
 */
function subsets(nums) {
  const result = [];

  // Backtracking helper: `start` is the current index in nums we are deciding on
  // `currentSubset` is the subset built so far.
  function backtrack(start, currentSubset) {
    if (start === nums.length) {
      // Reached the end of nums, record a copy of the current subset
      result.push([...currentSubset]);
      return;
    }
    // Choice 1: INCLUDE nums[start]
    currentSubset.push(nums[start]);
    backtrack(start + 1, currentSubset);
    // Backtrack step: remove the last included element
    currentSubset.pop();
    // Choice 2: EXCLUDE nums[start]
    backtrack(start + 1, currentSubset);
    // (No need to undo anything for the exclude case since we didn't modify currentSubset)
  }

  backtrack(0, []);  // start from index 0 with an empty subset
  return result;
}

// Example usage:
console.log(subsets([1, 2, 3]));
/* 
Output (order may vary):
[
  [1, 2, 3],
  [1, 2],
  [1, 3],
  [1],
  [2, 3],
  [2],
  [3],
  []
]
Each subset of [1,2,3] is listed. 
*/

Explanation: We define backtrack(start, currentSubset):

• If start is beyond the last index, we’ve formed a complete subset and push a copy of it to result.

• Otherwise, we consider the element at nums[start]. We first include it (push it into currentSubset), then recurse to build subsets of the remaining elements. After returning, we undo the inclusion (pop it out). Next, we excludethe element and recurse without it.

• The currentSubset is a running list of chosen elements. We use result.push([...currentSubset]) to record a snapshot, because currentSubset is mutated in place during recursion.

• This algorithm runs in O(2^n) time, generating all 2^n subsets. Space complexity is O(n) for the recursion stack (not counting the output).

You can see the two branches for each element clearly in this approach. For [1,2,3], the recursion explores subsets in this order: include 1 (then include 2, include 3 -> [1,2,3], backtrack, exclude 3 -> [1,2], backtrack to 2), exclude 2 (include 3 -> [1,3], backtrack, exclude 3 -> [1], backtrack to 1), then exclude 1 (include 2, include 3 -> [2,3], and so on…). This is one depth-first traversal of the power set tree.

Solved Example: Subsets with Duplication Handling

Now, let’s consider LeetCode 90 – Subsets II, where the input array may contain duplicates. The challenge here is to avoid returning duplicate subsets (e.g., if the input has [1,2,2], the subset [2] should appear only once, not twice for each “2”).

Problem: Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets.

Approach: We can use a similar backtracking strategy as before, but we need to handle duplicates. A common technique is to sort the array first, and then when backtracking, skip over subsequent duplicate values when they are being considered as new additions. Specifically, when we choose to exclude an element, we want to ensure we don’t then include a duplicate of that element in a parallel branch at the same recursion depth.

Tip: When iterating through candidates in backtracking, a rule of thumb for avoiding duplicates is: if the next candidate is the same as the previous one, skip it unless the previous one was chosen in the current path. In an include/exclude context, this translates to skipping the “include” branch for a duplicate if the duplicate immediately follows a copy of itself that was excluded.

However, a simpler approach for subsets: iterate through the array and generate subsets by considering each element in turn (rather than strict include/exclude recursion). For each unique value, handle the branching. Here we present a solution using an iterative-recursive hybrid approach:

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);  // sort to group duplicates
  const result = [];

  function backtrack(start, currentSubset) {
    // Record the subset built so far
    result.push([...currentSubset]);

    for (let i = start; i < nums.length; i++) {
      // If this value is the same as the previous one at the same depth, skip it
      if (i > start && nums[i] === nums[i - 1]) {
        continue;  // avoid duplicate subset paths
      }
      // Include nums[i] and move deeper
      currentSubset.push(nums[i]);
      backtrack(i + 1, currentSubset);
      currentSubset.pop();  // backtrack (remove nums[i] and try next possibility)
    }
  }

  backtrack(0, []);
  return result;
}

// Example:
console.log(subsetsWithDup([1, 2, 2]));
/*
Expected Output (order may vary):
[
  [], 
  [1], 
  [2], 
  [1, 2], 
  [2, 2], 
  [1, 2, 2]
]
Notice that [2] appears only once, and all unique subsets are listed.
*/

Explanation: We use a loop inside backtrack to iterate through candidates starting from index start. This is another style of backtracking (especially common for combinations): at each call, we decide which next element to include (or not) by looping through the options. The important part is skipping duplicates:

• After sorting, duplicates are adjacent. The condition if (i > start && nums[i] === nums[i-1]) continue;ensures that at a given recursion depth, we only take the first occurrence of a series of equal numbers. For example, at start=0 with [1,2,2], when i=1 we include the first 2, but when i=2 (the second 2), since nums[2] === nums[1] and i > start, we skip to avoid starting a new subset branch with the second 2 (that branch would be redundant with the one started by the first 2).

• We still record every subset (including the empty set at the initial call).

• This approach effectively prunes branches that would produce duplicate subsets. The result is all unique subsets.

This pattern of skipping duplicates by sorting and checking adjacent elements is a recurring trick in backtracking problems (you’ll see it again in combinations and permutations with duplicates). It’s a form of pruning that drastically reduces the search space when duplicates are present.

Pattern 2: Combinations (Choose-k or Target-based Selection)

The Combinations pattern builds on the idea of subsets but typically adds additional constraints: for example, “choose exactly k items out of n” or “choose items that meet a certain criterion (like summing to X).” Instead of an implicit include/exclude for every element, combination problems often involve deciding which specific elements to pick out of a collection, usually without regard to order (i.e., {1,2} is considered the same combination as {2,1} and should only appear once).

This pattern’s backtracking approach usually involves controlling the recursion such that combinations are generated without permutations of the same combination. A common strategy is to use an index and ensure we only move forward (never reuse previous elements unless allowed in the problem). Many combination problems ask for all combinations of a certain size or that satisfy a specific property (like a sum).

How the Combinations Pattern Works

Key characteristics of combination pattern problems:

• We are choosing a subset of items (like the subsets pattern) but often with a fixed size k or a condition (like a target sum).

• Order does not matter for the final combination (combinations {1,2} and {2,1} are considered the same).

• To avoid generating duplicates or permutations of the same combo, the backtracking typically uses a start indexand iterates forward.

• We might allow repeated use of the same element in some cases (like “combination sum” where you can pick the same number multiple times), or not allow repeats (choose distinct elements).

Common problem structures: Generate all combinations of k elements out of n (e.g., “Combinations” problem), find combinations of numbers that sum to a target (without or with repetition allowed), or generate combinations from multiple groups (like picking one item from each category). Problems like “n choose k” selections, coin change combinations, or any scenario of “select some items that fulfill a requirement” fall in this category.

Decision-making logic: We typically use recursion with a loop:

• We maintain a start index for where to pick the next element from, ensuring we don’t reuse elements before this index to avoid duplicates.

• We iterate i from start to end:

  • Pick nums[i] (include it in current combination).

  • Recurse with start = i+1 (move to next elements) if each element can only be used once. (If elements can be reused, we might call recurse with start = i to allow the same element again).

  • Backtrack (remove nums[i] and try the next i).

• We also track additional state like current sum or current count of elements to know when we’ve hit the combination criteria.

• Base cases: if the combination reaches the desired size or sum, record it; if it exceeds the desired sum/size, prune the branch.

Tips and tricks:

• Avoiding permutations: Always ensure that you never consider an element twice in the same combination. This is achieved by advancing the start index after choosing an element. It inherently prevents picking an element earlier than its index again.

• For “exactly k elements” combinations, you can stop recursion when the combination’s length equals k (and only record those of length k). Additionally, you can prune if the combination’s length + remaining elements < k (i.e., not enough elements left to reach k).

• For “target sum” combinations, sort the array first. This helps to prune branches (stop exploring further if sum exceeds target) and also skip duplicates (skip identical numbers as in subsets II).

• If repeats are allowed (like unlimited supply of an element), you recurse without incrementing the index (or you use the same i again) so that the element can be chosen multiple times.

• Many combination problems are solved with a loop inside the backtracking function that tries each possible next element (this is sometimes called the “DFS with for-loop” pattern).

• The complexity depends on the size of combinations. For choosing k out of n, there are C(n, k) combinations; for sum problems, it can vary based on how the numbers combine to target.

Example Problems for Combinations Pattern

Here are 10 practice problems exemplifying the combinations pattern:

(Note: Some of these, like Palindrome Partitioning or Phone Letter Combos, can also be seen as decision tree pattern. The lines between patterns are blurry – what matters is recognizing the backtracking approach needed. We list them here if the core task is choosing combinations of pieces.)

Solved Example: Combinations (n choose k)

Let’s solve LeetCode 77 – Combinations, a fundamental combinations problem:

Problem: Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

For example, if n=4 and k=2, the output should be all 2-number combinations from {1,2,3,4}, i.e.: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Approach: We need to generate combinations of length k. We will use backtracking with the following logic:

• Use a helper backtrack(start, combo) where start is the next number to consider and combo is the current combination being built.

• If combo.length == k, we have a complete combination; add a copy of it to results.

• Otherwise, iterate i from start to n:

  • Add i to the combination.

  • Recurse with backtrack(i+1, combo) to fill the next position.

  • Remove i (backtrack) and continue to the next i.

• We initialize backtrack(1, []) because we can start choosing from 1.

We will also add a simple pruning: if the current combination length plus the number of remaining choices is less than k, we can break early (no need to continue). For example, if we have already chosen 2 out of 5 and only 1 number is left to choose but k=4, it’s impossible to reach length 4.

function combine(n, k) {
  const result = [];

  function backtrack(start, combo) {
    // If the combination is complete
    if (combo.length === k) {
      result.push([...combo]);
      return;
    }
    // If not enough elements remaining to reach k, we can stop (prune)
    // (Optional optimization)
    if (combo.length + (n - start + 1) < k) {
      return; // not enough numbers left to complete a combo of length k
    }

    for (let num = start; num <= n; num++) {
      combo.push(num);            // choose num
      backtrack(num + 1, combo);  // explore further with next numbers
      combo.pop();                // un-choose num (backtrack)
    }
  }

  backtrack(1, []);
  return result;
}

// Example:
console.log(combine(4, 2));
// Expected output (order can differ): 
// [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ]

Explanation: The function backtrack(start, combo) tries all numbers from start to n as the next pick for the combination. We add the number, recurse, and then remove it. The start ensures we never pick a smaller number after a larger one, so combinations are generated in lexicographical order without duplicates. For instance, after picking 1, the next picks will start at 2 (so we get [1,2], [1,3], [1,4]); once we backtrack from starting with 1, we then start with 2 (giving [2,3], [2,4]), then 3 (giving [3,4]), etc.

The optional pruning check if (combo.length + (n - start + 1) < k) return; helps avoid useless iterations. If combo.length = 1 and start = 5 in a n=6, k=4 scenario, then remaining = 6-5+1 = 2 numbers left, plus the 1 already in combo = 3, which is less than k (4). So we know it's impossible to reach length 4 from there, and we cut off the recursion early.

This approach runs in O(C(n, k) * k) approximately, since we generate C(n, k) combinations and each combination takes O(k) to construct/copy. For small k relative to n, this is quite efficient.

Solved Example: Combination Sum (with Pruning)

Now consider LeetCode 39 – Combination Sum, which introduces a target sum constraint and allows reusing elements. This is a classic combinations-with-target problem.

Problem: Given an array of distinct candidate numbers and a target sum, find all unique combinations of candidates where the chosen numbers sum to the target. You may use each candidate number multiple times. The combinations can be returned in any order.

Example: candidates = [2,3,6,7], target = 7. Solutions: [[7], [2,2,3]] (because 7 itself or 2+2+3 achieve target 7).

Approach: We use backtracking to build combinations that accumulate to the target:

• Sort the candidates (not strictly necessary here since they’re distinct and can be reused, but good practice especially if we later handle duplicates).

• Use a helper backtrack(start, combination, currentSum).

• If currentSum == target, we found a valid combination – record it.

• If currentSum > target, we can stop exploring this path (prune, since adding more will only increase sum).

• Otherwise, for each index i from start to end of candidates:

  • Include candidates[i] and recurse with updated sum.

  • Since we can reuse the same number, we call backtrack(i, ...) (not i+1).

  • Remove the number and try the next candidate.

• We use start index to avoid counting combinations multiple times in different order. By not resetting the index to 0 for each call (passing i for reuse or i+1 for move on), we ensure combinations are built in non-decreasing order of indices, avoiding duplicates.

Pruning: We stop exploring a branch as soon as the sum exceeds the target, because candidates are positive (assuming positive integers, which is given in this problem).

function combinationSum(candidates, target) {
  candidates.sort((a,b) => a - b);  // sort for consistency and potential pruning
  const result = [];

  function backtrack(start, currentCombo, currentSum) {
    if (currentSum === target) {
      result.push([...currentCombo]);
      return;
    }
    if (currentSum > target) {
      return; // prune: exceeded the target
    }
    for (let i = start; i < candidates.length; i++) {
      const num = candidates[i];
      // If the current sum + this number is > target, we can break (prune further numbers as well, since array is sorted)
      if (currentSum + num > target) break;
      currentCombo.push(num);
      backtrack(i, currentCombo, currentSum + num); // `i` instead of `i+1` because we can reuse same number
      currentCombo.pop();
    }
  }

  backtrack(0, [], 0);
  return result;
}

// Example:
console.log(combinationSum([2,3,6,7], 7));
// Output: [ [2,2,3], [7] ]

Explanation: We iterate through candidates starting at start. The key difference from the simple combination generation is the currentSum tracking and the prune conditions:

• If currentSum goes over target, we stop exploring deeper on that path.

• We also break out of the loop early if adding the current number would exceed the target (if (currentSum + num > target) break;). This is effective because we sorted the array; any larger number beyond this will also exceed the target.

• We allow the same index i again in recursion (backtrack(i, ...)) to reuse the candidate. For example, starting with 2, we can again choose 2 (stay at i) to accumulate multiples of 2.

• Once we move past a number (in the loop, when i increments), we won’t use that number again in higher recursion levels, ensuring combinations are unique (e.g., [2,2,3] is generated once).

This problem demonstrates how pruning drastically reduces the search: without the if > target break check, the recursion would explore many unnecessary branches. With pruning, the search tree is cut off as soon as the sum is too large.

Pattern 3: Permutations (Ordering Pattern)

The Permutations pattern involves arranging items in all possible orders. Unlike subsets or combinations, here order matters. When generating permutations via backtracking, we typically build sequences by picking an element for each position. This pattern often requires careful handling to avoid using the same element more than once in a given permutation (unless duplicates are allowed, in which case additional checks are needed to avoid duplicate permutations).

How the Permutations Pattern Works

For permutations of n distinct elements:

• There are n! (n factorial) possible permutations.

• We can generate them by taking each element as a possible first element, then recursively permuting the remaining elements.

• A common approach is to maintain a boolean array (or use a set) to mark which elements are already included in the current permutation, or physically remove elements from a list as we build the permutation.

• Each level of recursion fixes one position in the permutation, and the depth of recursion equals n (the length of permutation).

Common problem structures: Generating all permutations of a list or string (distinct or with duplicates), generating all arrangements subject to certain conditions (like all orderings of tasks, or all anagrams of a word). Also, some sequencing problems can be viewed as permutation generation with pruning (e.g., find a permutation that satisfies a condition).

Decision-making logic: Two popular implementations:

1. Swap method (in-place): Swap each possible element into the current index, then recurse for the next index, and swap back. This uses the array itself to represent the current state.

2. Visited array method: Keep a visited boolean array for which elements have been added to the current permutation so far. Recurse by trying all elements that are not yet visited.

In either case:

• Base case: when the current permutation’s length equals n (or when we’ve placed all elements), record the permutation.

• Otherwise, iterate over the elements:

  • If using visited array: for each element not visited, mark it visited and add to current permutation, recurse, then un-mark and remove it.

  • If using swap method: for each index from current index to end, swap, recurse (with current index + 1), then swap back.

• Handle duplicates: If input has duplicate values, you should skip generating permutations that are duplicates (commonly by sorting and skipping adjacent equal values when they haven’t been used yet, or by ensuring only one of identical elements at a given recursion level is chosen).

Tips and tricks:

• Using a visited array and a separate list for the current permutation is very straightforward to implement.

• When dealing with duplicates, sort the input and when iterating, skip an element if it’s the same as a previous element that wasn’t visited in this recursion call (this prevents duplicate permutation generation).

• Permutation problems can explode in complexity (n! permutations). Often n is relatively small (like <= 8 or 9) in interview questions. For larger n, you would not generate all permutations explicitly.

• Some problems ask for the k-th permutation (like “Permutation Sequence” – LeetCode 60) which can be solved mathematically rather than generating all.

• If constraints are added (e.g., “permutations that satisfy X condition”), incorporate those as pruning conditions in the recursion (e.g., skip constructing permutations that violate the condition early).

Visualization analogy: Imagine building a permutation as arranging people in chairs. You have n people and n chairs. You choose someone for the first chair (n options), then for the second chair (n-1 options), and so on. Backtracking can simulate this by placing each person and then recursively placing the rest. The decision tree is n-ary (not binary like subsets) – from each state, you have as many branches as remaining choices. The tree’s leaves are the full permutations.

Example Problems for Permutations Pattern

Practice problems focusing on permutations and related concepts:

(Many of the above “Hard” examples are more about illustrating how permutations tie into other problems. In interviews, the most common tasks are generating permutations (with or without duplicates) and perhaps using permutations as part of a brute-force solution to an optimization problem (with pruning).)

Solved Example: Permutations of Distinct Numbers

We’ll solve LeetCode 46 – Permutations as a straightforward example.

Problem: Given an array of distinct integers, return all possible permutations of the array.

Example: nums = [1,2,3] -> Output should be all 6 permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].

Approach: We use backtracking with a visited array:

• backtrack(path) where path is the current permutation being built.

• If path.length == nums.length, record a copy of path (one full permutation).

• Otherwise, loop through each number in nums. If it’s not yet in path (we track this with a boolean visited array), choose it: mark as visited, add to path, recurse, then unmark and remove from path.

This will generate permutations in lexicographic order if nums is sorted (if we want lexicographic, we can sort first, though it’s not required here since any order is fine).

function permute(nums) {
  const result = [];
  const visited = Array(nums.length).fill(false);

  function backtrack(currentPermutation) {
    if (currentPermutation.length === nums.length) {
      result.push([...currentPermutation]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (visited[i]) continue;  // skip already used element
      // Choose nums[i]
      visited[i] = true;
      currentPermutation.push(nums[i]);
      backtrack(currentPermutation);
      // Backtrack: undo the choice
      currentPermutation.pop();
      visited[i] = false;
    }
  }

  backtrack([]);
  return result;
}

// Example:
console.log(permute([1,2,3]));
/* Output (order may vary):
[
  [1,2,3], [1,3,2],
  [2,1,3], [2,3,1],
  [3,1,2], [3,2,1]
]
*/

Explanation: The visited array ensures we only use each index once per permutation. The recursion depth goes from 0 to n (length of nums):

• At depth 0, we try each element as the first element (1, then 2, then 3).

• At depth 1 (say we picked 1 already), we try remaining elements as second (if 1 is picked, try 2 then 3 as second).

• Depth 2, place the last remaining element.

• Depth 3 (base case), permutation is complete – record it.

• Then backtrack: remove the last element and try another, etc.

Since the input has distinct integers, we don’t need special duplicate handling. The algorithm inherently generates each permutation once. The time complexity is O(n * n!) (there are n! permutations, and copying them or constructing them takes O(n) each). This is fine for moderate n (like n <= 7 or 8 in interviews).

Solved Example: Permutations with Duplicates

To demonstrate handling duplicates, let’s solve LeetCode 47 – Permutations II:

Problem: Given a collection of numbers that might contain duplicates, return all unique permutations.

Example: nums = [1,1,2] -> The distinct permutations are [[1,1,2],[1,2,1],[2,1,1]] (3 permutations instead of 3! = 6, because duplicates reduce the count).

Approach: We can modify the previous solution:

• Sort the array nums. This way, duplicates are adjacent.

• Use a visited array as before.

• When iterating through nums for choices, skip an element if it’s the same as the previous element and the previous element has not been used in the current permutation yet. In other words, if nums[i] == nums[i-1]and !visited[i-1], skip i. This ensures that we only take the first of a series of equal numbers at a given position in the permutation tree.

This condition prevents generating permutations that only differ in swapping identical elements. Essentially, it prunes branches that would lead to duplicate outcomes.

function permuteUnique(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  const visited = Array(nums.length).fill(false);

  function backtrack(currentPerm) {
    if (currentPerm.length === nums.length) {
      result.push([...currentPerm]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (visited[i]) continue;              // already used this element in current permutation
      if (i > 0 && nums[i] === nums[i-1] && !visited[i-1]) continue;  // skip duplicates
      // Choose nums[i]
      visited[i] = true;
      currentPerm.push(nums[i]);
      backtrack(currentPerm);
      // Undo choice
      currentPerm.pop();
      visited[i] = false;
    }
  }

  backtrack([]);
  return result;
}

// Example:
console.log(permuteUnique([1,1,2]));
// Expected unique permutations: [ [1,1,2], [1,2,1], [2,1,1] ]

Explanation: The critical line is:

if (i > 0 && nums[i] === nums[i-1] && !visited[i-1]) continue;

This ensures that if we have a duplicate number and the identical number right before it is not yet used in the current permutation path, we skip using this one. Another way to think about it: we only allow the first occurrence of a set of equal numbers to be picked at a permutation position; subsequent ones are skipped until the first is used (marked visited in the current recursion path). By sorting, nums[i-1] is the "previous twin" of nums[i]. If nums[i-1] is not visited, it means in the current branch we haven't placed that number yet, and taking nums[i] first would lead to the same permutations as if we took nums[i-1] first (just swapping the two identical values). So we prune that branch.

This way, the algorithm generates each distinct permutation exactly once. The complexity is still O(n * n!) in the worst case (if all elements are distinct), but in cases with duplicates it is less (effectively n! divided by the multiplicities of duplicates).

Pattern 4: Decision Tree (Multi-step Decision & Path Exploration)

The Decision Tree pattern is a broad category for backtracking problems that involve making a sequence of decisions that aren’t just simple include/exclude or straightforward permutations/combinations. These are problems where at each step, you have multiple possible choices or moves, and you need to explore those systematically. This pattern often applies to constructing sequences, paths, or configurations under certain rules, and it doesn’t map one-to-one to a small set of input elements like the previous patterns.

In many ways, all backtracking can be thought of as traversing a decision tree (Backtracking Demystified: The Algorithm Pattern That Powers Problem Solving - TeddySmith.IO). We highlight this pattern for cases that involve more free-form decision making, such as building valid strings, exploring moves in a grid, or partitioning things in ways other than picking from a list.

How the Decision Tree Pattern Works

Key aspects:

• You define a state (could be partial solution, position in a grid, prefix of a string, etc.).

• From that state, you determine all possible valid moves or choices you can make next.

• For each choice, you change the state accordingly and recursively solve the subproblem from the new state.

• You backtrack by undoing the move to restore the state and try the next choice.

This is essentially a DFS on a graph of states (often implicitly represented by recursion). The “tree” is the recursion tree of decisions.

Common problem structures: Balanced parentheses generation, pathfinding in a maze or grid (moving up/down/left/right), constructing strings or sequences under certain constraints (like placing queens on a chessboard row by row, which is also a decision sequence), breaking a problem into multiple parts (like partitioning a string into palindromes or IP address segments – each cut is a decision), or exploring game moves (e.g., all possible moves in a puzzle). In other words, any problem where you have to explore a space of possibilities by making a series of choices can fall here if it doesn’t neatly fit the earlier patterns.

Decision-making logic: Unlike subsets/permutations where the choices are typically picking from a set of discrete items, here the choices might be generated by the state:

• In a maze, the choices are which direction to move.

• In generating parentheses, the choice is whether to add '(' or ')' at a given step (with the caveat that it must form a valid prefix).

• In partitioning a string, the choice is where to cut the string next (or which prefix to take).

• In placing queens, the choice is which column to place a queen in for the current row.

The backtracking function often takes a state representation (like current index or position, partial constructed output, etc.) and explores all valid next states:

• Check if the state is a complete solution (e.g., string fully constructed, reached target cell, all required items placed, etc.).

• Otherwise, determine all possible next actions from this state that maintain validity.

• Loop over those actions, apply one, recurse, then undo it.

Tips and tricks:

• For path problems (maze, graphs), maintain a visited structure to avoid cycles (so you don’t revisit the same state infinitely).

• For sequence construction (like generating strings), use constraints to prune. E.g., in generating balanced parentheses of length 2n, at any point you cannot add a ')' if there aren’t more '(' already added (must stay valid prefix). This drastically prunes the search.

• Representing the state properly is important. For complex state (like a Sudoku board configuration), writing helper functions to check validity can help.

• These problems often benefit from insights or specific strategies: e.g., symmetry in N-Queens (you can reduce search by symmetry), or prefix pruning in word search (stopping if current prefix doesn’t match any word in dictionary).

• The branching factor might be large if not pruned (for example, at each empty cell in Sudoku you have up to 9 choices), so effective pruning and constraints checking are key to make it tractable.

• Many of these problems are famous interview questions or competitive programming tasks – having seen the pattern before will help, as you recognize how to break down the decisions.

Example Problems for Decision Tree Pattern

This category is broad. Here are 10 problems that exemplify decision-tree style backtracking:

(Some problems here intersect with combinations; we list them again to emphasize the decision sequence view. They require more complex decision logic than a straightforward subset/pick.)

Solved Example: Generate Parentheses

One of the most classic backtracking problems is LeetCode 22 – Generate Parentheses.

Problem: Given n, generate all combinations of well-formed parentheses with n pairs of ().

Example: n=3 -> Output: ["((()))","(()())","(())()","()(())","()()()"] (all 5 valid combinations of 3 pairs of parentheses).

Approach: This is a decision sequence problem. We need to build a string of length 2n consisting of n '(' and n ')' in a valid order. A prefix of a valid parentheses string is never supposed to have more ')' than '(' (you can’t close more brackets than opened at any point). We use two counters:

• open: how many '(' have been used so far.

• close: how many ')' have been used so far.

At each step:

• We can add '(' if open < n (we still have some left to place).

• We can add ')' if close < open (we have more opens that need closing).

We start with an empty string and at each decision add either '(' or ')' if allowed, recursively building until the string length is 2n.

This effectively prunes a huge portion of the search space because it never even tries an invalid prefix (like "())("). The recursion tree can be thought of as binary (at each step two choices, down to depth 2n), but many branches are cut off early due to the constraints.

function generateParenthesis(n) {
  const result = [];

  function backtrack(current, openCount, closeCount) {
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }
    // If we can still add an '(', do it.
    if (openCount < n) {
      backtrack(current + "(", openCount + 1, closeCount);
    }
    // If we can add a ')', do it. (We need more '(' placed than ')' to add ')')
    if (closeCount < openCount) {
      backtrack(current + ")", openCount, closeCount + 1);
    }
  }

  backtrack("", 0, 0);
  return result;
}

// Example:
console.log(generateParenthesis(3));
// Output: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]

Explanation: We use a helper backtrack(currentString, openCount, closeCount). The conditions:

• If the current string length is 2n, we have placed all parentheses and it’s a valid combination (if we respected the rules while building). We add it to results.

• We can add '(' if we still have some left to add (openCount < n).

• We can add ')' if there are more opens than closes in the current prefix (closeCount < openCount). This ensures validity of prefix.

• We explore both possibilities (if allowed), effectively doing a DFS in the space of balanced parentheses strings.

For n=3, it starts:

• ( (open=1, close=0) -> (( (2,0) -> ((( (3,0) -> now openCount == n, can’t add (, only ) -> ((() (3,1) -> continue adding ) when possible... and so on). It will backtrack and try other branches (like at (( it will also try adding ) to get ((), etc.).

This problem demonstrates how adding constraints (here, the well-formed rule) prunes the decision tree. Without constraints, there would be C(2n, n) sequences to consider (combinatorial), but invalid ones are never generated.

Solved Example: Word Search (Backtracking in a Grid)

Let’s tackle LeetCode 79 – Word Search to illustrate backtracking on a grid (a pathfinding problem):

Problem: Given an m x n board of characters and a word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically neighboring). A cell can only be used once in the word.

This is a search problem where we try to find a path in the grid that matches the given word.

Approach: We will try to build the word letter by letter by moving around the grid:

• Loop through each cell in the board as a potential starting point.

• Use backtracking DFS from that cell:

  • Keep an index pos into the word (which letter we’re trying to match next).

  • At each step, if the current cell’s character matches word[pos], then we explore its neighbors (up to 4 directions) for word[pos+1].

  • Mark the current cell as visited (to avoid re-using it in this path).

  • Recurse to neighbor cells with pos+1.

  • If at any point pos == word.length (we matched all letters), return true.

  • If a path doesn’t work out, backtrack: unmark the cell and return false up that path.

• If any path returns true (found the word), stop and return true. If all start positions fail, return false.

We need a visited structure. We can modify the board in-place (e.g., temporarily set used cells to a special character) or use a separate visited matrix. We’ll use a simple in-place approach for brevity: set the used cell to # or something and set it back when backtracking.

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r, c, pos) {
    if (pos === word.length) {
      return true;  // successfully matched all letters
    }
    // Check boundaries and if current cell matches the needed letter
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[pos]) {
      return false;
    }
    // Mark this cell as visited by using a placeholder
    const temp = board[r][c];
    board[r][c] = '#';  // mark as visited
    // Explore all four directions
    const found = dfs(r+1, c, pos+1) || dfs(r-1, c, pos+1) ||
                  dfs(r, c+1, pos+1) || dfs(r, c-1, pos+1);
    board[r][c] = temp;  // restore the original letter (backtrack)
    return found;
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (dfs(i, j, 0)) {
        return true;
      }
    }
  }
  return false;
}

// Example:
const board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
];
console.log(exist(board, "ABCCED")); // true (A->B->C->C->E->D path exists)
console.log(exist(board, "SEE"));    // true (S->E->E path exists)
console.log(exist(board, "ABCB"));   // false

Explanation: We define dfs(r, c, pos) as “does the word from position pos onward exist starting from cell (r,c)?”. The function checks bounds and if the current cell matches word[pos]. If not, it fails. If yes, and if pos is the last index of the word, we found the whole word. If not at end, we mark the cell as visited (here by setting it to '#') and explore neighbors for the next character. If any neighbor returns true (meaning it found the rest of the word), we bubble true up. We always restore the cell’s letter after exploring neighbors (backtracking step).

This is a typical DFS/backtracking on a grid. The worst-case complexity is O(m*n * 4^L) where L is word length (each step has up to 4 moves). Pruning occurs when characters don’t match or we hit visited cells/out of bounds, which in practice makes it feasible for short words.

The decision tree here branches up to 4 ways at each step (less on edges). We used a simple heuristic: checking the character match to decide whether to proceed or prune a branch.

Pattern 5: Constraint Satisfaction (Pruning and Search)

The Constraint Satisfaction pattern is an advanced form of backtracking where the goal is to assign values to a set of variables subject to constraints. Classic examples include N-Queens, Sudoku, graph coloring, cryptarithmetic puzzles, and others. These problems usually have a significant number of possibilities, so success relies on pruning invalid partial solutions early and using heuristics to reduce search.

In these problems, backtracking systematically searches through the space of possible assignments and prunes those that violate constraints, thereby significantly cutting down the search space (The N-queens Problem | OR-Tools - Google for Developers) (Eight queens puzzle - Wikipedia). Each “decision” often assigns a value to one variable (e.g., place a queen in a row, assign a number to a Sudoku cell, give a color to a node) and then checks constraints before moving on.

How the Constraint Satisfaction Pattern Works

General approach:

• Identify variables to assign (positions in Sudoku, rows for queens, graph nodes for coloring, letters for cryptarithm, etc.).

• Choose an unassigned variable (often use heuristics like the most constrained variable first to prune faster).

• Iterate over possible values for that variable (e.g., possible numbers, possible positions).

• If a value violates a constraint (even with previously assigned variables), skip it (prune that branch).

• If it’s consistent, assign it and recursively assign the rest.

• If all variables are assigned and all constraints satisfied, a solution is found.

• Backtrack by unassigning and trying a different value if needed.

Common problem structures:

• N-Queens: place queens so none attack each other (constraint: no two queens share a row, col, or diagonal).

• Sudoku: fill grid so each row, col, and 3x3 box has all digits 1-9 (multiple constraints).

• Graph coloring: color nodes so no adjacent nodes share a color (constraint on edges).

• Word puzzles: like crossword filling or word squares, where letters must satisfy across/down constraints.

• Cryptarithm (alphametic puzzles): assign digits to letters such that an addition/subtraction equation holds (constraints on sums, unique digits, etc).

• Magic squares, KenKen, Kakuro, etc.: various puzzle rules.

• Others: sometimes combination sum or partition problems can be seen in this light if heavily constrained.

Decision-making logic: Often one variable (or one step) at a time:

• Place a queen in the next row – try each column, but check if it’s safe (no conflict with existing queens).

• Fill the next empty Sudoku cell – try digits 1-9 that satisfy not already in same row/col/box.

• Assign a color to the next graph node that isn’t used by neighbors.

• If at any point no valid assignment is possible (no choices or all choices lead to conflict), backtrack.

Pruning techniques: This is where CSP backtracking shines:

• Forward checking: Once you assign a value, eliminate that value from the domain of neighboring variables (e.g., when you place a queen, mark that column and diagonals unavailable for others).

• Arc consistency (AC-3): A more advanced technique ensuring that binary constraints are consistent ahead of time.

• Heuristics like MRV (minimum remaining values): choose the next variable that has the fewest legal values left to try – this can find dead-ends faster.

• Symmetry breaking: e.g., in N-Queens, you can assume the first queen is in a certain column by symmetry to cut solutions that are reflections/rotations.

• Memoization: In some problems like Sudoku, memoizing possible candidates for each cell can speed up checks.

• Realize that many of these problems have known solution counts or results (e.g., N-Queens has known number of solutions for small n; it’s often used as an example problem for backtracking and constraint solving (Eight queens puzzle - Wikipedia)).

Tips:

• Write helper functions to check constraints quickly (like isValid(board, row, col, val) for Sudoku or queen placement).

• Use data structures to track used values (like sets for rows/cols/boxes in Sudoku to quickly test a number’s validity).

• It’s often effective to combine backtracking with some level of greedy or constraint propagation to reduce the search space (like fill obvious cells first).

• Know when to backtrack early: the moment a partial assignment violates a constraint, return false immediately.

• These problems can be expensive (Sudoku has an enormous search space if done naively), but with constraints guiding the search, typical puzzles are solvable in reasonable time.

Example Problems for Constraint Satisfaction Pattern

Some classic problems that are solved via backtracking + constraints:

(These are advanced and often time-consuming problems – but they showcase the power of backtracking augmented with constraints. Many have more efficient specialized algorithms, but backtracking is a general approach that will work given enough pruning.)

Solved Example: N-Queens

We will work through LeetCode 51 – N-Queens as a prime example of a constraint satisfaction problem.

Problem: Place n queens on an n x n chessboard such that no two queens attack each other. (Queens attack vertically, horizontally, and diagonally.)

For example, one solution for n=4 is:

. Q . .    (Q at row0,col1)
. . . Q    (Q at row1,col3)
Q . . .    (Q at row2,col0)
. . Q .    (Q at row3,col2)

which corresponds to solution [1,3,0,2] in terms of queen column positions per row.

We need to return all distinct solutions, each solution being a board arrangement or a list of column indices for queens in each row.

Approach: Backtracking row by row:

• We will have an array cols of length n, where cols[r] = c means queen in row r is at column c.

• We place queens one row at a time. For each row, we try each column and check if it’s safe (no queen in same column or diagonals).

• We maintain sets (or arrays) to mark which columns are occupied, and which diagonals are occupied. We can represent diagonals by indices: for a queen at (r,c):

  • “Main” diagonal index = r-c (this can be negative, so offset by +n to use as index in array)

  • “Anti” diagonal index = r+c We ensure no other queen shares these indices.

• When we reach row == n (past the last row), we found a solution. We then translate the cols array into the requested output format (like an array of strings with 'Q' and '.').

We’ll implement it with sets for simplicity (one for columns, one for main diagonals, one for anti diagonals). We could also use boolean arrays of size n (for columns) and size 2n (for diagonals) for efficiency.

(image) One of the solutions for the 8-Queens puzzle (8 queens on an 8×8 board). Backtracking systematically finds such solutions by placing queens row by row and pruning invalid placements (Eight queens puzzle - Wikipedia).

function solveNQueens(n) {
  const results = [];
  const colsUsed = new Set();
  const mainDiagUsed = new Set();
  const antiDiagUsed = new Set();
  const cols = Array(n);

  function backtrack(row) {
    if (row === n) {
      // Construct solution from cols array
      const board = cols.map(colIndex => {
        let rowStr = '.'.repeat(n);
        return rowStr.substring(0, colIndex) + 'Q' + rowStr.substring(colIndex+1);
      });
      results.push(board);
      return;
    }
    for (let col = 0; col < n; col++) {
      const mainDiag = row - col;
      const antiDiag = row + col;
      if (colsUsed.has(col) || mainDiagUsed.has(mainDiag) || antiDiagUsed.has(antiDiag)) {
        continue; // conflict, skip this column
      }
      // Place queen at (row, col)
      cols[row] = col;
      colsUsed.add(col);
      mainDiagUsed.add(mainDiag);
      antiDiagUsed.add(antiDiag);
      // Recurse to next row
      backtrack(row + 1);
      // Remove queen (backtrack)
      colsUsed.delete(col);
      mainDiagUsed.delete(mainDiag);
      antiDiagUsed.delete(antiDiag);
      // (cols[row] will be overwritten in next iteration or on backtrack up, so no need to clear it explicitly)
    }
  }

  backtrack(0);
  return results;
}

// Example:
console.log(solveNQueens(4));
// Output: One possible result (order may vary):
// [
//   [".Q..","...Q","Q...","..Q."],
//   ["..Q.","Q...","...Q",".Q.."]
// ]
// These correspond to the two distinct solutions for 4-queens.

Explanation: We attempt to place a queen in each column of the current row and check for conflicts:

• colsUsed tracks columns that already have queens.

• mainDiagUsed tracks r-c values used by queens.

• antiDiagUsed tracks r+c values used.

If placing at (row, col) is safe (not in any set), we mark those sets and recurse to row+1. If we reach row === n, it means we placed queens in all rows successfully – we then construct the board representation and add to results.

Backtracking: we remove the col and diagonal marks as we return from recursion (which unreserves that column/diagonals for future tries).

Using sets (or boolean arrays) makes the constraint checks O(1), so the limiting factor is the number of placements we try. The algorithm essentially tries n^n possibilities in the worst unconstrained scenario, but the constraints heavily prune it. For N-Queens, known algorithms with backtracking can solve n=8 quickly (92 solutions) and even n=9,10, etc., though it’s exponential. (For interviews, n is often small or just for the concept.)

This problem demonstrates constraint satisfaction:

• Early on, many columns are pruned because they conflict with already placed queens.

• Without pruning, placing 8 queens would involve checking 16 million possibilities (8^8); with pruning, it’s vastly reduced (only 92 solutions exist with much fewer partial checks).

• It’s a classic example used to illustrate backtracking and constraint solving (Eight queens puzzle - Wikipedia), showing how backtracking makes an otherwise intractable search feasible by eliminating impossible placements early.

Solved Example: Sudoku Solver

For a final example, let’s briefly outline the Sudoku Solver (LeetCode 37), which is more complex. We won’t write the full code due to length, but we’ll describe the approach as it follows the pattern:

Problem: Fill a 9x9 Sudoku grid with digits so that each row, column, and 3x3 subgrid contains all digits 1-9 exactly once. Some cells are pre-filled.

Approach: Use backtracking to fill empty cells:

• Find an empty cell (row, col).

• Determine which digits (1-9) are valid in that cell (not already in that row/col/box).

• For each valid digit, place it and recurse to fill the next empty cell.

• If at some point an empty cell has no valid moves (all 1-9 conflict), backtrack.

• Continue until all cells are filled.

Techniques:

• Use three sets/arrays to track used numbers in each row, each column, and each 3x3 subgrid.

• You can use a single index for subgrid like boxIndex = Math.floor(row/3)*3 + Math.floor(col/3) to map (row,col) to one of 9 subgrid indices.

• This tracking allows O(1) checking of whether a number can be placed.

• Use recursion to move to the next empty cell. For efficiency, you might pick the empty cell with the fewest possibilities (MRV heuristic) to prune faster.

• When a solution is found (board filled), you can stop (Sudoku has a unique solution typically or you just need one solution).

This algorithm tries potentially up to 9^81 combinations in the worst naive sense, but the constraint checks prune massively. Real Sudoku puzzles are designed to be solvable with backtracking + inference quickly.

While we won’t list full code here, the implementation would mirror N-Queens but with a 9x9 grid and three constraint sets (rows, cols, boxes). After each assignment, mark the number as used in that row/col/box, etc. When backtracking, unmark.

This illustrates how backtracking solves a real-world puzzle – one that people solve with logic, which the algorithm mirrors by trying possibilities and undoing when a contradiction is reached.

Pattern 6: Pruning Techniques in Backtracking

Throughout all the above patterns, we’ve mentioned pruning – cutting off branches of the search space that we know won’t lead to a valid solution or that would lead to duplicate work. Pruning is not a separate kind of problem, but rather a crucial technique to incorporate into backtracking solutions to make them efficient enough for practical use.

However, it’s worth explicitly summarizing common pruning techniques and seeing them in action, since recognizing opportunities to prune is key to writing optimal backtracking solutions. Here we list some common pruning strategies, with examples:

1. Validity pruning: Immediately skip (do not recurse into) any branch that violates a problem constraint.

   • Example: In N-Queens, if a queen threatens another, we don’t place the second queen and explore that branch.

   • Example: In Sudoku, if a number is already present in the row/col/box, don’t try that number in the empty cell.

2. Bound pruning (Optimistic pruning): If you’re accumulating a value (like a sum, or length), and it exceeds a target or cannot possibly reach a target, prune.

   • Example: Combination Sum – if current sum > target, break out of loop (further additions only increase it) (Combinations and Permutations with an Intro to Backtracking | by Nick Ma | Medium).

   • Example: If picking k numbers and you have more picks left than remaining items (as in Combinations), break (not enough elements left to reach k).

   • Example: In optimization problems like the Traveling Salesman, if current path cost + a heuristic < best found, prune (branch and bound).

3. Duplicate pruning: Avoid exploring permutations or combinations that are essentially the same due to duplicate input values.

   • Example: Permutations II – skip subsequent duplicate elements at the same recursion depth (Combinations and Permutations with an Intro to Backtracking | by Nick Ma | Medium) (Combinations and Permutations with an Intro to Backtracking | by Nick Ma | Medium).

   • Example: Subsets II – skip generating subsets starting with a duplicate value that’s identical to a previously handled value in that call.

   • Example: Increasing Subsequences – when picking next element, skip duplicates to avoid same subsequence appearing multiple times.

4. State memoization: Remember states you have visited to avoid re-computation (this turns backtracking into DFS with memo, often).

   • Example: Word Break II (finding all sentences that form a string) – use a memo for substring -> list of sentences to avoid re-solving for the same substring multiple times.

   • Example: In a maze, keep a visited set of positions to avoid infinite loops or redundant paths (though for acyclic or small grids this is more about correctness than optimization).

   • This is more like DP, but sometimes combined (backtracking with memo = DFS with memoization).

5. Ordering heuristics: Not exactly pruning, but improves efficiency by making pruning happen earlier:

   • Example: In Sudoku, choosing the next empty cell with the fewest possible numbers (most constrained) often leads to quicker failure if it’s wrong, cutting search.

   • Example: In 8-Queens, some people try to place queens in middle columns first to reduce symmetric branches, etc.

   • These heuristics reduce the size of the tree that needs exploring.

The effect of pruning is often dramatic. Without pruning, many backtracking problems are hopelessly exponential; with it, they become tractable.

Example Problems Highlighting Pruning

These problems have already been discussed, but here we focus on the pruning aspect in each:

Pruning in Code (Mini Examples)

To solidify, here are quick snippets illustrating pruning in some contexts:

• Prune on sum (Combination Sum):

    if (currentSum > target) {
        // no need to proceed further down this path
        return;
    }
  

  Or inside a loop with sorted candidates:

    for (let i = start; i < nums.length; i++) {
        if (currentSum + nums[i] > target) break; // stop, all further nums[j] (j>i) will also make sum too large
        // ... proceed with including nums[i]
    }
  

• Prune duplicates (Subset II / Permutations II):

    if (i > start && nums[i] === nums[i-1]) continue;
  

  In permutations with visited tracking:

    if (i > 0 && nums[i] === nums[i-1] && !visited[i-1]) continue;
  

  This skips the scenario where a duplicate value is chosen out of order.

• Prune on constraints (N-Queens row/col/diag):

    if (colsUsed.has(col) || diagUsed.has(r-c) || antiDiagUsed.has(r+c)) {
        continue; // conflict, skip this column
    }
  

  This prevents placing a queen where it can attack or be attacked.

• Visited state pruning (Word Search):

    function dfs(r, c, pos) {
      if (...) return false;
      let tmp = board[r][c];
      board[r][c] = '#'; // mark visited
      // explore neighbors
      board[r][c] = tmp; // unmark
    }
  

  Without marking visited, the DFS might loop back and reuse cells.

By applying these kinds of checks, the algorithm focuses only on promising branches. It’s often the difference between an algorithm timing out vs. running quickly.

Conclusion and Next Steps

We have explored a comprehensive set of backtracking patterns:

• Subsets pattern: simple include/exclude decisions (power set generation).

• Combinations pattern: choosing sets of items meeting criteria (with controlled recursion and forward-only selection).

• Permutations pattern: arranging items in order (with visited markers and possibly swaps).

• Decision tree pattern: general scenarios of step-by-step decisions (from generating strings like parentheses to traversing grids or making moves in a game).

• Constraint satisfaction pattern: complex problems with strict rules requiring pruning (N-Queens, Sudoku, puzzles).

• Pruning techniques: cross-cutting methods to optimize all the above.

For each pattern, we provided detailed explanations, tips, and example problems, along with solved examples in JavaScript to illustrate the approaches. The code examples demonstrated how to implement the backtracking template (“choose, explore, unchoose” (Combinations and Permutations with an Intro to Backtracking | by Nick Ma | Medium)) in practice for different scenarios.

When preparing for competitive programming or coding interviews, it’s wise to:

• Practice identifying which pattern a new problem fits into. Many interview problems are slight twists on the above examples.

• Write out the backtracking recursion by hand for a small example to ensure you understand the decision tree.

• Implement the solution while carefully adding pruning conditions and testing on simple cases.

• Be comfortable with both recursive and iterative (stack) implementations of these patterns, though recursion is usually more straightforward for conceptual clarity.

• Also, be aware of the time complexity – know when backtracking might be too slow without pruning or when a different approach is needed (e.g., DP or greedy). But for combinatorial generation problems, backtracking is often the idiomatic solution.

Mastery comes with practice: try solving variations of the listed problems. For instance, after doing “Subsets”, try “Subsets II” to solidify duplicate handling. After “Generate Parentheses”, one might try similar problems like “Binary Strings with no consecutive 1s” (a decision tree with a constraint). After “Sudoku”, a simpler one like “KenKen” might be doable with the same principles.

Backtracking is a brute-force search, but a smart one – it’s about being clever in systematically exploring possibilities and cutting off those that won’t work. With these patterns and techniques in mind, you can confidently tackle a wide array of problems that require exploring possibilities, whether in interviews or contests. Good luck, and happy backtracking!