Backtracking is an algorithmic technique that builds solutions incrementally, abandoning a path as soon as it determines the path cannot lead to a valid solution (pruning).
// General backtracking template:
function backtrack(candidate) {
if (isValid(candidate)) {
output(candidate);
return;
}
for (const next of getCandidates(candidate)) {
place(next);
backtrack(next);
remove(next); // undo the choice (backtrack)
}
}
Backtracking is used for constraint satisfaction problems like N-Queens, Sudoku, and subset generation.
Place N queens on an N×N board so no two queens attack each other. Use backtracking: place queens row by row and check column and diagonal conflicts.
function solveNQueens(n) {
const result = [], board = [];
function isSafe(row, col) {
for (let i = 0; i < row; i++) {
if (board[i] === col || Math.abs(board[i] - col) === row - i)
return false;
}
return true;
}
function solve(row) {
if (row === n) { result.push([...board]); return; }
for (let col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row] = col;
solve(row + 1);
}
}
}
solve(0);
return result;
}
Time: O(n!) | Explores and prunes invalid placements.
Fill empty cells one by one. For each empty cell, try digits 1-9, check validity, and backtrack if stuck.
function solveSudoku(board) {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] === 0) {
for (let num = 1; num <= 9; num++) {
if (isValid(board, r, c, num)) {
board[r][c] = num;
if (solveSudoku(board)) return true;
board[r][c] = 0; // backtrack
}
}
return false; // no valid number found
}
}
}
return true; // all cells filled
}
Time: O(9<sup>(empty cells)</sup>) worst case, but pruning makes it practical.
A rat starts at (0,0) and must reach (n-1, n-1) in a maze where 1 = open path and 0 = blocked. The rat can move down or right. Backtrack when blocked.
function ratInMaze(maze) {
const n = maze.length;
const path = Array.from({length: n}, () => new Array(n).fill(0));
function solve(r, c) {
if (r === n-1 && c === n-1 && maze[r][c] === 1) {
path[r][c] = 1;
return true;
}
if (r < n && c < n && maze[r][c] === 1) {
path[r][c] = 1;
if (solve(r + 1, c) || solve(r, c + 1)) return true;
path[r][c] = 0; // backtrack
}
return false;
}
solve(0, 0);
return path;
}
Time: O(2<sup>n²</sup>) worst | Space: O(n²)
Given a 2D board and a word, check if the word exists by moving to adjacent cells (up/down/left/right). Each cell can be used only once per path.
function wordSearch(board, word) {
const rows = board.length, cols = board[0].length;
function dfs(r, c, idx) {
if (idx === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
if (board[r][c] !== word[idx]) return false;
const temp = board[r][c];
board[r][c] = "#"; // mark visited
const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1)
|| dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
board[r][c] = temp; // backtrack
return found;
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (dfs(r, c, 0)) return true;
return false;
}
Time: O(m × n × 4<sup>L</sup>) where L = word length
Build permutations by choosing each unused element, adding it to the current path, and backtracking after the recursive call.
function permutations(nums) {
const result = [];
function backtrack(path, used) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
backtrack(path, used);
path.pop(); // backtrack
used[i] = false;
}
}
backtrack([], new Array(nums.length).fill(false));
return result;
}
// permutations([1,2,3]) => [[1,2,3],[1,3,2],[2,1,3],...]
Time: O(n × n!) | Space: O(n)
For combinations of size k from n elements, use a start index to avoid duplicates and backtrack after each choice.
function combinations(n, k) {
const result = [];
function backtrack(start, combo) {
if (combo.length === k) {
result.push([...combo]);
return;
}
for (let i = start; i <= n; i++) {
combo.push(i);
backtrack(i + 1, combo);
combo.pop(); // backtrack
}
}
backtrack(1, []);
return result;
}
// combinations(4, 2) => [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Time: O(C(n, k)) | Space: O(k)
Find all subsets of an array that sum to a target. Include or exclude each element and prune when the running sum exceeds the target.
function subsetSum(nums, target) {
const result = [];
nums.sort((a, b) => a - b);
function backtrack(idx, current, sum) {
if (sum === target) { result.push([...current]); return; }
for (let i = idx; i < nums.length; i++) {
if (sum + nums[i] > target) break; // prune
current.push(nums[i]);
backtrack(i + 1, current, sum + nums[i]);
current.pop();
}
}
backtrack(0, [], 0);
return result;
}
// subsetSum([2, 3, 5, 7], 7) => [[2,5], [7]]
Time: O(2<sup>n</sup>) worst case | Pruning reduces actual computation.
Map each digit to letters (like a phone keypad) and generate all possible letter combinations using backtracking.
function letterCombinations(digits) {
if (!digits) return [];
const map = { "2":"abc","3":"def","4":"ghi","5":"jkl",
"6":"mno","7":"pqrs","8":"tuv","9":"wxyz" };
const result = [];
function backtrack(idx, path) {
if (idx === digits.length) { result.push(path); return; }
for (const ch of map[digits[idx]]) {
backtrack(idx + 1, path + ch);
}
}
backtrack(0, "");
return result;
}
// letterCombinations("23") => ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Time: O(4<sup>n</sup>) where n = number of digits
Partition a string so every substring is a palindrome. Try all possible partitions and backtrack when a substring is not a palindrome.
function palindromePartition(s) {
const result = [];
function isPalin(str, l, r) {
while (l < r) { if (str[l++] !== str[r--]) return false; }
return true;
}
function backtrack(start, parts) {
if (start === s.length) { result.push([...parts]); return; }
for (let end = start; end < s.length; end++) {
if (isPalin(s, start, end)) {
parts.push(s.slice(start, end + 1));
backtrack(end + 1, parts);
parts.pop();
}
}
}
backtrack(0, []);
return result;
}
// palindromePartition("aab") => [["a","a","b"], ["aa","b"]]
Time: O(n × 2<sup>n</sup>) | Space: O(n)
Try each digit 1-9 in empty cells. Skip if the digit conflicts with the current row, column, or 3×3 box. Backtrack if no valid digit exists.
function solveSudoku(board) {
function isValid(r, c, num) {
const boxR = Math.floor(r / 3) * 3, boxC = Math.floor(c / 3) * 3;
for (let i = 0; i < 9; i++) {
if (board[r][i] === num) return false; // same row
if (board[i][c] === num) return false; // same col
if (board[boxR + Math.floor(i/3)][boxC + i%3] === num) return false; // 3x3 box
}
return true;
}
function solve() {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] === '.') {
for (let d = 1; d <= 9; d++) {
const ch = String(d);
if (isValid(r, c, ch)) {
board[r][c] = ch;
if (solve()) return true;
board[r][c] = '.'; // backtrack
}
}
return false; // no valid digit
}
}
}
return true; // all cells filled
}
solve();
}
// Input: 9x9 board with some cells filled
// Output: board modified in-place with valid solution
Time: O(9^m) where m = empty cells | Space: O(m)
Sort the array first. In the loop, skip duplicates at the same recursion level (if nums[i] === nums[i-1] and i > start, skip).
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [];
function backtrack(start, current) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
// Skip duplicates at the same tree level
if (i > start && nums[i] === nums[i-1]) continue;
current.push(nums[i]);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
// Input: [1,2,2]
// Output: [[],[1],[1,2],[1,2,2],[2],[2,2]] (no duplicate subsets)
Time: O(2ⁿ × n) | Space: O(n)
Move right or down (or all 4 directions). At each cell, mark it visited, try all valid moves, then unmark (backtrack) if no path found.
function ratMaze(maze, n) {
const paths = [];
const visited = Array.from({length: n}, () => new Array(n).fill(false));
const dirs = [[1,0,'D'],[-1,0,'U'],[0,1,'R'],[0,-1,'L']];
function solve(r, c, path) {
if (r === n-1 && c === n-1) { paths.push(path); return; }
for (const [dr, dc, dir] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& maze[nr][nc] === 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
solve(nr, nc, path + dir);
visited[nr][nc] = false; // backtrack
}
}
}
if (maze[0][0] === 1) { visited[0][0] = true; solve(0, 0, ''); }
return paths;
}
// Input: [[1,0,0,0],[1,1,0,1],[0,1,0,0],[0,1,1,1]]
// Output: ["DDRDRR","DRDDRR"]
Time: O(4^(n²)) worst | Space: O(n²)
Candidates can be reused. At each step, either use the current candidate again (same index) or move to the next. Backtrack by removing the last choice.
function combinationSum(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
function backtrack(start, remaining, current) {
if (remaining === 0) { result.push([...current]); return; }
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // pruning
current.push(candidates[i]);
backtrack(i, remaining - candidates[i], current); // reuse allowed
current.pop(); // backtrack
}
}
backtrack(0, target, []);
return result;
}
// Input: candidates=[2,3,6,7], target=7 => Output: [[2,2,3],[7]]
// Input: candidates=[2,3,5], target=8 => Output: [[2,2,2,2],[2,3,3],[3,5]]
Time: O(n^(target/min)) | Space: O(target/min)
Try placing dots at 3 positions (splitting into 4 parts). Each part must be 1-3 digits, no leading zeros, and value ≤ 255.
function restoreIpAddresses(s) {
const result = [];
function backtrack(start, parts) {
if (parts.length === 4) {
if (start === s.length) result.push(parts.join('.'));
return;
}
for (let len = 1; len <= 3; len++) {
if (start + len > s.length) break;
const segment = s.slice(start, start + len);
// No leading zeros, value <= 255
if (segment.length > 1 && segment[0] === '0') break;
if (Number(segment) > 255) break;
backtrack(start + len, [...parts, segment]);
}
}
backtrack(0, []);
return result;
}
// Input: "25525511135" => Output: ["255.255.11.135","255.255.111.35"]
// Input: "0000" => Output: ["0.0.0.0"]
Time: O(1) — max 3^4 = 81 combinations | Space: O(1)
For each cell, start a DFS. Mark cell visited, try all 8 neighbors that match the next character. Backtrack by unmarking the cell.
function exist(board, word) {
const rows = board.length, cols = board[0].length;
function dfs(r, c, idx) {
if (idx === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[idx]) return false;
const tmp = board[r][c];
board[r][c] = '#'; // mark visited
const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1)
|| dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
board[r][c] = tmp; // restore (backtrack)
return found;
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (dfs(r, c, 0)) return true;
return false;
}
// Input: board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"
// Output: true
Time: O(rows × cols × 4^len) | Space: O(len)
Sort the array. Use a used boolean array. Skip a duplicate if its preceding equal element was not used in the current path (prevents same ordering from being generated twice).
function permuteUnique(nums) {
nums.sort((a, b) => a - b);
const result = [], used = new Array(nums.length).fill(false);
function backtrack(current) {
if (current.length === nums.length) { result.push([...current]); return; }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
// Skip duplicate: same value used at this position in a previous branch
if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
used[i] = true;
current.push(nums[i]);
backtrack(current);
current.pop();
used[i] = false;
}
}
backtrack([]);
return result;
}
// Input: [1,1,2] => Output: [[1,1,2],[1,2,1],[2,1,1]]
// Input: [1,2,3] => Output: 6 permutations (no duplicates)
Time: O(n!) | Space: O(n)
Find the last occurrence of each character. Greedily extend the current partition's end to cover all characters seen so far. When current position reaches the end, record a part.
function partitionLabels(s) {
const last = {};
for (let i = 0; i < s.length; i++) last[s[i]] = i;
const result = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]); // extend to cover all occurrences
if (i === end) {
result.push(end - start + 1);
start = i + 1;
}
}
return result;
}
// Input: "ababcbacadefegdehijhklij"
// Output: [9,7,8] ("ababcbaca","defegde","hijhklij")
// Input: "eccbbbbdec" => Output: [10]
Time: O(n) | Space: O(1) — at most 26 characters
Try all 8 knight moves from the current position. Use Warnsdorff's heuristic (choose the move with the fewest onward moves) to prune efficiently.
function knightsTour(n) {
const board = Array.from({length: n}, () => new Array(n).fill(-1));
const moves = [[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]];
board[0][0] = 0;
function solve(r, c, moveNum) {
if (moveNum === n * n) return true;
for (const [dr, dc] of moves) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] === -1) {
board[nr][nc] = moveNum;
if (solve(nr, nc, moveNum + 1)) return true;
board[nr][nc] = -1; // backtrack
}
}
return false;
}
return solve(0, 0, 1) ? board : null;
}
// Input: n=5 => Output: 5x5 board where each cell has a unique move number
// Input: n=8 => Output: 8x8 complete knight's tour
Time: O(8^(n²)) worst, much better with Warnsdorff | Space: O(n²)
Insert each operator combination between digits. Track accumulated value and the last multiplied term (for correct multiplication precedence).
function addOperators(num, target) {
const result = [];
function backtrack(index, path, value, prev) {
if (index === num.length) {
if (value === target) result.push(path);
return;
}
for (let len = 1; len <= num.length - index; len++) {
const str = num.slice(index, index + len);
if (str.length > 1 && str[0] === '0') break; // no leading zeros
const curr = BigInt(str);
if (index === 0) {
backtrack(len, str, curr, curr);
} else {
backtrack(index + len, path + '+' + str, value + curr, curr);
backtrack(index + len, path + '-' + str, value - curr, -curr);
backtrack(index + len, path + '*' + str, value - prev + prev * curr, prev * curr);
}
}
}
backtrack(0, '', 0n, 0n);
return result;
}
// Input: num="123", target=6 => Output: ["1+2+3","1*2*3"]
// Input: num="232", target=8 => Output: ["2*3+2","2+3*2"]
Time: O(4^n × n) | Space: O(n)
Recursively find all factors from 2 to sqrt(n). Each factor and the reduced quotient form a pair. Backtrack after recording each valid combination.
function getFactors(n) {
const result = [];
function backtrack(n, start, current) {
if (current.length > 0) result.push([...current, n]);
for (let f = start; f * f <= n; f++) {
if (n % f === 0) {
current.push(f);
backtrack(n / f, f, current); // recurse with reduced n
current.pop(); // backtrack
}
}
}
backtrack(n, 2, []);
return result;
}
// Input: 12 => Output: [[2,6],[2,2,3],[3,4]]
// Input: 37 => Output: [] (prime, no factors)
// Input: 32 => Output: [[2,16],[2,2,8],[2,2,2,4],[2,2,2,2,2],[4,8]]
Time: O(n log n) | Space: O(log n)
Use BFS to try removing each bracket. First level where a valid string is found = minimum removals. Use a Set to avoid re-processing duplicates.
function removeInvalidParentheses(s) {
const isValid = str => {
let count = 0;
for (const c of str) {
if (c === '(') count++;
else if (c === ')') { if (--count < 0) return false; }
}
return count === 0;
};
const result = [], visited = new Set([s]);
let queue = [s], found = false;
while (queue.length) {
const next = [];
for (const cur of queue) {
if (isValid(cur)) { result.push(cur); found = true; }
if (found) continue;
for (let i = 0; i < cur.length; i++) {
if (cur[i] !== '(' && cur[i] !== ')') continue;
const candidate = cur.slice(0, i) + cur.slice(i + 1);
if (!visited.has(candidate)) { visited.add(candidate); next.push(candidate); }
}
}
if (found) break;
queue = next;
}
return result.length ? result : [''];
}
// Input: "()())()" => Output: ["(())()","()()()"]
// Input: "(a)())()" => Output: ["(a())()","(a)()()"]
Time: O(n × 2^n) | Space: O(n × 2^n)