Patterns

Recursively build candidates; choose, recurse, undo (push/pop)

When to usePermutations, combinations, subsets, generate parentheses

recursive

Generate All Valid Parentheses

generate_parentheses

Max Length Of A Concatenated String With Unique Characters

max_length_of_a_concatenated_string_with_unique_characters

Find All Combination of Numbers that Sum to a Target | Shopping Options

amazon_oa_find_all_combination_of_numbers_sum_to_target

Backtracking Template

backtracking

Backtracking - Counting Problems

backtracking_alternate

Backtracking with Pruning

combine_numbers · no slots

Concatenated String Length with unique Characters

concatenated_string_length_with_unique_characters

Generate All Letter Combinations from a Phone Number

letter_combinations_of_phone_number

Partitioning A String Into Palindromes

palindrome_partitioning

General All Permutations

permutations

Split String Into Unique Primes

split_string_into_unique_primes

amazon_oa_number_game

Partition to K Equal Sum Subsets

partition_k_equal_sum_subsets

Combinationsmedium

combinations · no slots

Subsets IImedium

subsets_ii · no slots

Sudoku Solverhard

sudoku_solver · no slots

BASE CASE

if path satisfies completion criteria, push to result and return

if (current.length === 2 * n) { result.push(current); return; }

maxLen = Math.max(maxLen, path.length);

if (remaining === 0) { result.push([...path]); return; }

if (start === n) { result.push(path.join('')); return; }

if (position === n) { count += 1; return; }

if (remaining === 0) { count += 1; return; }
if (index === sorted.length) return;

if (remaining === 0) { result.push([...path]); return; }

—

maxLen = Math.max(maxLen, charSet.size);

if (startIndex === digits.length) { result.push(path.join('')); return; }

if (start === s.length) { result.push([...path]); return; }

if (current.length === letters.length) { result.push(current); return; }

if (start === s.length) { count++; return; }

result.push([...current]); // snapshot at entry — every path is valid

result.push([...current]); // snapshot at entry — every path is valid

if (remaining === 0) return true;

if (remainingGroups === 0) return true;
if (currentSum === target) return backtrack(remainingGroups - 1, 0, 0);

—

EXPLORE

for each choice in remaining options

if (open < n) backtrack(current + '(', open + 1, close);
if (close < open) backtrack(current + ')', open, close + 1);

for (let i = start; i < arr.length; i++) {

for (let i = start; i < nums.length; i++) {

for (const letter of 'ab') {

// try placing 0 (always valid); try placing 1 (only if lastBit === 0)

// binary branch: include element or exclude it

for (let i = start; i < candidates.length; i++) {

—

for (let i = start; i < candidates.length; i++) {

for (const letter of KEYBOARD[digits[startIndex]]) {

for (let end = start + 1; end <= s.length; end++) {

for (let i = 0; i < letters.length; i++) {

for (let end = start + 1; end <= s.length; end++) {

for (let i = start; i < nums.length; i++) {

for (let i = start; i < nums.length; i++) {

for (let j = i + 1; j <= n; j++) {

for (let i = startIndex; i < sorted.length; i++) {

—

CHOOSE

path.push(choice)

—

  // path advances implicitly via next string

  path.push(nums[i]);

  path.push(letter);

  // choice is implicit — baked into recursive call arguments

  // include:

  path.push(candidates[i]);

—

  for (const c of candidates[i]) charSet.add(c);

  path.push(letter);

  path.push(s.substring(start, end));

  used[i] = true;

  used.add(Number(piece));

  current.push(nums[i]);

  current.push(nums[i]);

  used[j] = true;

  used[i] = true;

—

RECURSE

backtrack with updated state

—

  backtrack(i + 1, next);

  backtrack(nums, remaining - nums[i], i + 1, path, result);

  backtrack(start + 1);

  helper(position + 1, 0);
  if (lastBit === 0) helper(position + 1, 1);

  helper(index + 1, remaining - sorted[index]);
  helper(index + 1, remaining);

  backtrack(i, remaining - candidates[i]);

—

  backtrack(i + 1, charSet);

  backtrack(startIndex + 1, path);

  backtrack(end, path);

  backtrack(current + letters[i]);

  backtrack(end, used);

  backtrack(i + 1, current);

  backtrack(i + 1, current);

  if (backtrack(remaining - 2)) return true;

  if (backtrack(remainingGroups, currentSum + sorted[i], i + 1)) return true;

—

UNCHOOSE

path.pop()

—

  // no explicit pop — immutable string path

  path.pop();

  path.pop();

  // no path array — call stack unwinds automatically

  // no path array — state is in parameters, unwinds automatically

  path.pop();

—

  for (const c of candidates[i]) charSet.delete(c);

  path.pop();

  path.pop();

  used[i] = false;

  used.delete(Number(piece));

  current.pop();

  current.pop();

  used[j] = false;

  used[i] = false;

—

[FILTER]

skip choices that violate constraints (problem-specific)

// open < n guards '('; close < open guards ')'

  const next = path + arr[i];
  if (!isUnique(next)) continue;

  if (nums[i] > remaining) break;

—

  if (sorted[index] > remaining) return;

  if (candidates[i] > remaining) continue;

—

  if (candidates[i].split('').some(c => charSet.has(c))) continue;

—

  if (!isPalindrome(s.substring(start, end))) continue;

  if (used[i]) continue;

  const piece = s.slice(start, end);
  if (piece[0] === '0' || !isPrime(Number(piece)) || used.has(Number(piece))) continue;

—

  if (used[j] || !isPowerOfTwo(i + j)) continue;

  if (used[i] || currentSum + sorted[i] > target) continue;

—