回溯算法详解
回溯算法（Backtracking） 是一种通过试错的方式解决问题的算法，主要应用于组合、排列和求解约束满足问题（如数独、N皇后问题）。它通过构建问题的解空间树并在遍历时“回溯”来找到所有解或最优解。
核心思想
- 试探：将问题分解为多个子问题，逐步尝试。
- 约束条件：检查当前的尝试是否满足问题约束，如果不满足，则回溯。
- 回溯：撤销最近的选择，并尝试其他可能的选择。
伪代码
function backtrack(路径, 选择列表) {if (满足结束条件) {保存结果;return;}for (选择 in 选择列表) {做选择;backtrack(路径, 选择列表);撤销选择;}
}
常见回溯问题及代码
1. 全排列
function permute(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;path.push(nums[i]);used[i] = true;backtrack(path, used);path.pop();used[i] = false;}}backtrack([], Array(nums.length).fill(false));return result;
}
2. 子集
function subsets(nums) {const result = [];function backtrack(start, path) {result.push([...path]);for (let i = start; i < nums.length; i++) {path.push(nums[i]);backtrack(i + 1, path);path.pop();}}backtrack(0, []);return result;
}
3. 组合
function combine(n, k) {const result = [];function backtrack(start, path) {if (path.length === k) {result.push([...path]);return;}for (let i = start; i <= n; i++) {path.push(i);backtrack(i + 1, path);path.pop();}}backtrack(1, []);return result;
}
4. N皇后问题
function solveNQueens(n) {const result = [];const board = Array.from({ length: n }, () => Array(n).fill('.'));function isValid(row, col) {for (let i = 0; i < row; i++) {if (board[i][col] === 'Q') return false;if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;}return true;}function backtrack(row) {if (row === n) {result.push(board.map(row => row.join('')));return;}for (let col = 0; col < n; col++) {if (!isValid(row, col)) continue;board[row][col] = 'Q';backtrack(row + 1);board[row][col] = '.';}}backtrack(0);return result;
}
5. 数独求解
function solveSudoku(board) {function isValid(row, col, num) {for (let i = 0; i < 9; i++) {if (board[row][i] === num) return false;if (board[i][col] === num) return false;if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === num) return false;}return true;}function backtrack() {for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] !== '.') continue;for (let num = '1'; num <= '9'; num++) {if (!isValid(i, j, num)) continue;board[i][j] = num;if (backtrack()) return true;board[i][j] = '.';}return false;}}return true;}backtrack();
}
20个常见回溯问题
- 全排列（Permutations）
- 子集（Subsets）
- 组合（Combinations）
- N皇后问题（N-Queens）
- 数独求解（Sudoku Solver）
- 分割回文串（Palindrome Partitioning）
- 复原IP地址（Restore IP Addresses）
- 单词搜索（Word Search）
- 八皇后问题
- 组合总和（Combination Sum）
- 目标和（Target Sum）
- 排列序列（Permutation Sequence）
- 电话号码的字母组合（Letter Combinations of a Phone Number）
- 子集II（Subsets II，含重复元素）
- 跳跃游戏II（Jump Game II）
- 解数独（Sudoku Solver）
- 最大方形问题
- 棋盘覆盖问题
- 二维矩阵中岛屿的数量（Number of Islands）
- 迷宫路径求解
以下是所列问题的 JavaScript 代码实现：
1. 全排列（Permutations）
function permute(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;path.push(nums[i]);used[i] = true;backtrack(path, used);path.pop();used[i] = false;}}backtrack([], Array(nums.length).fill(false));return result;
}
2. 子集（Subsets）
function subsets(nums) {const result = [];function backtrack(start, path) {result.push([...path]);for (let i = start; i < nums.length; i++) {path.push(nums[i]);backtrack(i + 1, path);path.pop();}}backtrack(0, []);return result;
}
3. 组合（Combinations）
function combine(n, k) {const result = [];function backtrack(start, path) {if (path.length === k) {result.push([...path]);return;}for (let i = start; i <= n; i++) {path.push(i);backtrack(i + 1, path);path.pop();}}backtrack(1, []);return result;
}
4. N皇后问题（N-Queens）
function solveNQueens(n) {const result = [];const board = Array.from({ length: n }, () => Array(n).fill('.'));function isValid(row, col) {for (let i = 0; i < row; i++) {if (board[i][col] === 'Q') return false;if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;}return true;}function backtrack(row) {if (row === n) {result.push(board.map(r => r.join('')));return;}for (let col = 0; col < n; col++) {if (!isValid(row, col)) continue;board[row][col] = 'Q';backtrack(row + 1);board[row][col] = '.';}}backtrack(0);return result;
}
5. 数独求解（Sudoku Solver）
function solveSudoku(board) {function isValid(row, col, num) {for (let i = 0; i < 9; i++) {if (board[row][i] === num || board[i][col] === num || board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === num) {return false;}}return true;}function backtrack() {for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] !== '.') continue;for (let num = '1'; num <= '9'; num++) {if (!isValid(i, j, num)) continue;board[i][j] = num;if (backtrack()) return true;board[i][j] = '.';}return false;}}return true;}backtrack();
}
6. 分割回文串（Palindrome Partitioning）
function partition(s) {const result = [];function isPalindrome(start, end) {while (start < end) {if (s[start++] !== s[end--]) return false;}return true;}function backtrack(start, path) {if (start === s.length) {result.push([...path]);return;}for (let end = start; end < s.length; end++) {if (isPalindrome(start, end)) {path.push(s.slice(start, end + 1));backtrack(end + 1, path);path.pop();}}}backtrack(0, []);return result;
}
7. 复原IP地址（Restore IP Addresses）
function restoreIpAddresses(s) {const result = [];function backtrack(start, path) {if (path.length === 4) {if (start === s.length) result.push(path.join('.'));return;}for (let len = 1; len <= 3; len++) {if (start + len > s.length) break;const segment = s.slice(start, start + len);if (segment > 255 || (segment.length > 1 && segment[0] === '0')) break;path.push(segment);backtrack(start + len, path);path.pop();}}backtrack(0, []);return result;
}
8. 单词搜索（Word Search）
function exist(board, word) {function dfs(i, j, index) {if (index === word.length) return true;if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] !== word[index]) return false;const temp = board[i][j];board[i][j] = '#';const res = dfs(i + 1, j, index + 1) || dfs(i - 1, j, index + 1) || dfs(i, j + 1, index + 1) || dfs(i, j - 1, index + 1);board[i][j] = temp;return res;}for (let i = 0; i < board.length; i++) {for (let j = 0; j < board[0].length; j++) {if (dfs(i, j, 0)) return true;}}return false;
}
10. 组合总和（Combination Sum）
function combinationSum(candidates, target) {const result = [];function backtrack(start, path, sum) {if (sum === target) {result.push([...path]);return;}if (sum > target) return;for (let i = start; i < candidates.length; i++) {path.push(candidates[i]);backtrack(i, path, sum + candidates[i]);path.pop();}}backtrack(0, [], 0);return result;
}
归纳与总结
应用场景分类
- 排列组合问题：全排列、子集、组合、组合总和。
- 棋盘类问题：N皇后、数独、八皇后。
- 路径搜索问题：单词搜索、迷宫路径求解。
- 字符串分割问题：回文分割、复原IP地址。
- 图和网格问题：岛屿数量、最大方形问题。
优化方向
- 剪枝：在搜索时提前排除不符合条件的路径。
- 缓存（记忆化）：避免重复计算，常用于动态规划结合回溯。
- 迭代代替递归：避免递归栈溢出问题。
如果需要深入探讨具体问题，可以继续提出！