字符串反转、有重复数字的全排列和 N 皇后怎样用回溯写？

简答

反转字符串是热身题。LeetCode 344 给的是字符数组，要求原地修改、只用 O(1) 额外空间，所以用两个指针从两头往中间走，每次交换一对字符，走到中间就停。

全排列和 N 皇后都是回溯，写法都是“做选择、递归、撤销选择”。全排列每一步从还没用过的数里选一个放进路径；N 皇后每一行选一列放皇后，放完去下一行，回来时把皇后拿起来，再试下一列。

两道题的难点都在“哪些选择不能做”。全排列 II 的输入可能有重复数字，先排序让相同的数挨在一起，再规定相同的数只能从左到右依次使用，同一层就不会把两个相同的数各选一次。N 皇后用三个集合记下已经被占的列、主对角线（行减列相同）和副对角线（行加列相同），查一次就知道这个格子能不能放。

要注意，撤销必须和选择一一对应：选择时改了几处状态，撤销时就要改回几处，漏一处后面的分支就会出错。另外回溯是穷举，LeetCode 上 N 皇后的 n 最大只到 9，全排列 II 的长度最大只到 8。

字符串反转：双指针

LeetCode 344 的输入是字符数组 s，要求原地修改。下面用 left 和 right 两个下标从两头往中间走：

JavaScript

function reverseString(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
}

const chars = ['h', 'e', 'l', 'l', 'o'];
reverseString(chars);
console.log(chars.join('')); // olleh

const even = ['H', 'a', 'n', 'n', 'a', 'h'];
reverseString(even);
console.log(even.join('')); // hannaH

为什么条件是 left < right，而不是 left <= right？长度为奇数时，两个指针最后会停在同一个字符上，这个字符不用和自己交换。长度为偶数时，两个指针交换完最中间的一对后会交叉，循环自然结束。

如果输入是普通字符串，JavaScript 的字符串不能修改，常见写法是 str.split('').reverse().join('')。这种写法按 UTF-16 码元拆分，遇到表情符号这类由两个码元组成的字符会拆坏。题目里说明了字符都是可打印的 ASCII 字符，所以没有这个问题。

这道题和回溯无关，放在这里是因为它常和全排列一起被问到“字符串怎样处理”。回溯本身的模板见《回溯怎么写？全排列、子集和组合总和怎样做？》，下面只讲那道题没有展开的两道。

全排列 II：输入有重复数字怎样去重

LeetCode 47 给的 nums 可能有重复，要返回所有不重复的排列。比如 [1, 1, 2] 只有 3 种排列。如果直接用普通全排列的写法，两个 1 会被当成不同的元素，得到 6 个结果，其中每种都重复了一次。

去重的做法是先排序，再在循环里多加一个判断。看代码里 continue 的第二个条件：

JavaScript

function permuteUnique(nums) {
  const sorted = nums.slice().sort((a, b) => a - b);
  const result = [];
  const path = [];
  const used = new Array(sorted.length).fill(false);

  function backtrack() {
    if (path.length === sorted.length) {
      result.push(path.slice());
      return;
    }
    for (let i = 0; i < sorted.length; i++) {
      if (used[i]) continue;
      // 相同的数只能从左到右依次使用：左边那个还没用，就不能先用右边这个
      if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      path.push(sorted[i]); // 做选择
      backtrack(); // 递归
      path.pop(); // 撤销选择
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

console.log(JSON.stringify(permuteUnique([1, 1, 2]))); // [[1,1,2],[1,2,1],[2,1,1]]
console.log(permuteUnique([1, 2, 3]).length); // 6
console.log(permuteUnique([2, 2, 2]).length); // 1

这个判断为什么能去重？排序后两个 1 分别在下标 0 和 1。重复的排列来自同一位置先选了第二个 1、又选了第一个 1，排出来的数字顺序却一样。判断规定：第一个 1 还没用的时候，第二个 1 不能被选。这样两个 1 在任何路径里都只会按“先下标 0、后下标 1”的顺序出现，每种排列只会生成一次。

为什么一定要先排序？判断里比较的是 sorted[i] 和 sorted[i - 1]，只有相同的数挨在一起，比较相邻元素才能发现重复。没排序时，[1, 2, 1] 里的两个 1 不相邻，这个判断就失效了。

[2, 2, 2] 只有 1 种排列，结果也正好是 1，说明三个相同的数也只按一种顺序使用了。

N 皇后：每行放一个，三个集合判断冲突

N 皇后是在 n × n 的棋盘上放 n 个皇后，任意两个都不能互相攻击，也就是不能同行、同列、同一条对角线。LeetCode 51 要求返回所有解，每个解用字符串数组表示，'Q' 是皇后，'.' 是空格。

因为每行恰好有一个皇后，所以按行搜索：第 row 行在哪一列放，就是这一步的选择。同行的冲突自动排除了，剩下的冲突用三个 Set 记录：

JavaScript

function solveNQueens(n) {
  const result = [];
  const queens = []; // queens[row] 是第 row 行皇后所在的列
  const cols = new Set();
  const diag1 = new Set(); // 主对角线上 row - col 相同
  const diag2 = new Set(); // 副对角线上 row + col 相同

  function backtrack(row) {
    if (row === n) {
      result.push(queens.map((col) => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      // 做选择：放下皇后，三处占用一起记上
      queens.push(col);
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);
      backtrack(row + 1);
      // 撤销选择：三处占用一起清掉
      queens.pop();
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }

  backtrack(0);
  return result;
}

console.log(JSON.stringify(solveNQueens(4))); // [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
console.log(JSON.stringify(solveNQueens(1))); // [["Q"]]
console.log(solveNQueens(2).length); // 0
console.log(solveNQueens(8).length); // 92

为什么 row - col 能代表一条对角线？从左上往右下的一条斜线上，每往下走一行，列也加一，行和列的差不变。从右上往左下的斜线上，行加一、列减一，行和列的和不变。所以两个格子的 row - col 相同，就在同一条主对角线上；row + col 相同，就在同一条副对角线上。

为什么撤销要改四处？做选择时改了 queens、cols、diag1、diag2 四处状态，撤销时就要把四处都还原。假如漏掉 diag2.delete，这条对角线会一直被标记为占用，后面本来能放的格子会被误判为冲突，解就会变少。

n 为 2 和 3 时无解，所以 solveNQueens(2) 返回空数组。8 皇后一共有 92 个解。

复杂度和剪枝

N 皇后第一行有 n 种选法，第二行最多 n - 1 种，依此类推，所以搜索量的上界是 O(n!)。每找到一个解要拼出 n 个长度为 n 的字符串，花 O(n²)。用 Set 判断冲突是常数时间，比每次扫描已经放下的皇后要快。实际搜索量远小于 n!，因为冲突的格子在放下之前就被跳过了，这就是剪枝。

全排列 II 的结果数最多是 n!，每个结果拷贝花 O(n)，所以时间上界是 O(n × n!)，去重判断让重复的分支在第一层就被剪掉。

两道题的额外空间都是 O(n)，也就是路径、标记和递归调用栈，不算存结果的部分。

常见追问

全排列去重条件写成 used[i - 1] 而不是 !used[i - 1]，结果对吗？

结果也对，只是效率低一些。!used[i - 1] 规定相同的数从左到右使用，used[i - 1] 规定从右到左使用，两种规定都只保留一种顺序。区别是 used[i - 1] 这种写法会先走进很多最后凑不成完整排列的分支，剪枝发生得晚。拿 [1, 1, 1, 2, 2] 在 Node.js 里数递归调用次数，!used[i - 1] 是 34 次，used[i - 1] 是 99 次。

N 皇后只要求返回解的个数（LeetCode 52），代码怎么改？

把 result 换成一个计数器，row === n 时加一，不用拼字符串。搜索和撤销的逻辑完全一样。

为什么不用二维数组记录棋盘，然后每次检查横竖斜？

也可以，但每放一个皇后都要沿列和两条对角线扫描，检查一次要 O(n)。用三个集合记录列和对角线的编号，检查只要 O(1)。棋盘本身只在输出时才需要，所以只存每行皇后的列号就够了。