Backtracking Algorithm
Backtracking Algorithm
The Backtracking algorithm is a general technique used for solving problems by incrementally building solutions and abandoning those that fail to meet the criteria. It explores all possible solutions in a systematic manner and is particularly useful for constraint satisfaction and combinatorial problems.
Overview
Backtracking works by trying out all potential solutions and discarding those that do not meet the problem’s constraints. It builds a solution step-by-step, and if at any step the current solution does not meet the constraints, it backtracks to the previous step and tries a different option.
Algorithm Steps
- Choose: Select an option from the available choices.
- Explore: Move to the next state or option based on the current choice.
- Check: Determine if the current state meets the constraints or criteria of the problem.
- Backtrack: If the current solution path does not meet the criteria, revert to the previous state and try the next option.
Example Implementation
Code Example:
/**
* Solve [Problem Description] using Backtracking.
* @param {Type} [parameterName] - [Description of the parameter]
* @return {Type} - [Description of the return value]
*/
const [functionName] = ([parameters]) => {
const result = [];
const backtrack = (currentState) => {
// Base case: Check if current state meets the criteria
if ([condition]) {
result.push([solution]);
return;
}
// Iterate through options and recurse
for (const option of [options]) {
if ([isValid](option)) {
// Make a choice
[updateState](option);
// Recur to explore the next step
backtrack([newState]);
// Undo the choice (backtrack)
[revertState](option);
}
}
};
backtrack([initialState]);
return result;
};
// Example usage:
console.log([functionName]([testParameters]));
/* Output:
[Expected output]
*/
Rat in a Maze
const ratInMaze = (maze) => {
const n = maze.length;
const paths = [];
const path = [];
const directions = [
[1, 0, "D"], // Down
[0, -1, "L"], // Left
[0, 1, "R"], // Right
[-1, 0, "U"] // Up
];
const isSafe = (row, col, visited) => {
return (
row >= 0 && row < n &&
col >= 0 && col < n &&
maze[row][col] === 1 &&
!visited[row][col]
);
};
const backtrack = (row, col, visited) => {
if (row === n - 1 && col === n - 1) {
paths.push(path.join(""));
return;
}
visited[row][col] = true;
for (const [dx, dy, dir] of directions) {
const newRow = row + dx;
const newCol = col + dy;
if (isSafe(newRow, newCol, visited)) {
path.push(dir);
backtrack(newRow, newCol, visited);
path.pop(); // Backtrack
}
}
visited[row][col] = false;
};
if (maze[0][0] === 1) {
const visited = Array.from({ length: n }, () => Array(n).fill(false));
backtrack(0, 0, visited);
}
return paths;
};
// Example Usage
const maze = [
[1, 1, 1, 1],
[1, 1, 0, 1],
[0, 1, 0, 1],
[1, 1, 1, 1],
];
const result = ratInMaze(maze);
console.log(result);
/*
["DRDDRR", "DRURRDDD", "RDDDRR", "RRRDDD"]
*/
Count the Number of Paths
- Instead of listing all paths, count how many distinct paths exist from the top-left to the bottom-right corner.
const countPathsInMaze = (maze) => {
const n = maze.length;
let count = 0;
const isSafe = (row, col, visited) => {
return (
row >= 0 && row < n &&
col >= 0 && col < n &&
maze[row][col] === 1 &&
!visited[row][col]
);
};
const backtrack = (row, col, visited) => {
if (row === n - 1 && col === n - 1) {
count++;
return;
}
visited[row][col] = true;
const directions = [
[1, 0], // Down
[0, -1], // Left
[0, 1], // Right
[-1, 0], // Up
];
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (isSafe(newRow, newCol, visited)) {
backtrack(newRow, newCol, visited);
}
}
visited[row][col] = false; // Backtrack
};
if (maze[0][0] === 1) {
const visited = Array.from({ length: n }, () => Array(n).fill(false));
backtrack(0, 0, visited);
}
return count;
};
// Test Usage
const maze = [
[1, 1, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1],
];
console.log(countPathsInMaze(maze)); // Output: 2
N Queens
/**
* @param {number} n
* @return {string[][]}
*/
function solveNQueens(n) {
const solutions = [];
function solve(queens = [], row = 0) {
if (row === n) {
solutions.push(queens.map(col => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)));
return;
}
for (let col = 0; col < n; col++) {
if (queens.every((queenCol, queenRow) =>
queenCol !== col &&
Math.abs(queenCol - col) !== Math.abs(queenRow - row)
)) {
solve([...queens, col], row + 1);
}
}
}
solve();
return solutions;
}
Permutation
const permute = (nums) => {
const result = [];
const backtrack = (path) => {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (path.includes(nums[i])) continue;
path.push(nums[i]);
backtrack(path);
path.pop();
}
};
backtrack([]);
return result;
};
Permutation 2
const permuteUnique = (nums) => {
const list = []
nums.sort((a, b) => a - b); // Sort the array to ensure duplicates are adjacent
const backtrack = (tempList, used) => {
if (tempList.length === nums.length) {
list.push([...tempList]);
return
}
for (let i = 0; i < nums.length; i++) {
// Skip the used elements or duplicates
if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) continue;
used[i] = true;
tempList.push(nums[i]);
backtrack(tempList, used);
used[i] = false;
tempList.pop();
}
};
backtrack([], new Array(nums.length).fill(false));
return list;
};
Combination
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
const combine = (n, k) => {
const res = []
const backtrack = (index, comb) => {
if (comb.length === k) {
res.push([...comb])
return
}
for (let i = index; i < n + 1; i++) {
comb.push(i)
backtrack(i + 1, comb)
comb.pop()
}
}
backtrack(1, [])
return res
};
Combination Sum
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const combinationSum = (candidates, target) => {
const result = [];
const backtrack = (start, path, sum) => {
if (sum > target) return; // Exceeds the target, no need to continue
if (sum === target) { // Found a valid combination
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]); // Choose the candidate
backtrack(i, path, sum + candidates[i]); // Recur with the same candidate
path.pop(); // Backtrack, remove the last candidate
}
};
backtrack(0, [], 0); // Start with index 0, empty path, and sum 0
return result;
};
Combination 3
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
const combinationSum3 = (k, n) => {
const result = []
const backtrack = (start, path, sum) => {
if (path.length === k && sum === n) {
result.push([...path])
return
}
if (sum >= n && path.length >= k) return
for (let i = start; i <= 9; i++) {
path.push(i)
backtrack(i + 1, path, sum + i)
path.pop(i)
}
}
backtrack(1, [], 0)
return result
};
Subsets
/**
* @param {number[]} nums
* @return {number[][]}
*/
const subsets = (nums) => {
const result = []
const backtrack = (id, subs) => {
result.push([...subs])
for (let i = id; i < nums.length; i++) {
subs.push(nums[i])
backtrack(i + 1, subs)
subs.pop()
}
}
backtrack(0, [])
return result
};
Subsets 2
/**
* @param {number[]} nums
* @return {number[][]}
*/
const subsetsWithDup = (nums) => {
nums.sort((a, b) => a - b)
const result = []
const backtrack = (id, subs) => {
result.push([...subs])
for (let i = id; i < nums.length; i++) {
if (i > id && nums[i] === nums[i - 1]) continue
subs.push(nums[i])
backtrack(i + 1, subs)
subs.pop()
}
}
backtrack(0, [])
return result
};