C# 回溯算法：子集、排列与 N 皇后

一个模板，五道题。选择、探索、撤销选择——大家漏掉的往往是撤销选择，因为少了它，代码看起来也像写完了。

回溯是核心最小、用途最广的模式。这里的每道题都是同样三行，只是分支规则不同。

choose      — add to the current state
explore     — recurse
un-choose   — take it back out

第 13 篇的根到叶路径已经用过它。这一篇讲它真正的用武之地。

下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果粘贴过来。

模式 71 — 子集

求一个集合的所有子集。每个元素都有两种选择，所以搜索过程是一棵 n 层深的二叉树。

int[] a = [1, 2, 3];
List<List<int>> all = [];
List<int> current = [];

// The template every problem in this part is an instance of:
//   record the state, try each choice, UNDO the choice.
void Explore(int start, int depth)
{
    all.Add([.. current]);       // a copy — `current` keeps changing under us
    Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", current)}]");

    for (int i = start; i < a.Length; i++)
    {
        current.Add(a[i]);            // choose
        Explore(i + 1, depth + 1);    // explore, from AFTER i so nothing repeats
        current.RemoveAt(current.Count - 1);   // un-choose
    }
}

Explore(0, 0);
Console.WriteLine($"\n{all.Count} subsets, expected 2^{a.Length} = {1 << a.Length}");

// The same thing without recursion: each bit of a counter says include or not.
Console.WriteLine("\nby bitmask, no recursion at all:");
for (int mask = 0; mask < (1 << a.Length); mask++)
{
    var pick = Enumerable.Range(0, a.Length).Where(i => (mask & (1 << i)) != 0).Select(i => a[i]);
    Console.WriteLine($"  {Convert.ToString(mask, 2).PadLeft(a.Length, '0')} -> [{string.Join(",", pick)}]");
}

输出：

[]
  [1]
    [1,2]
      [1,2,3]
    [1,3]
  [2]
    [2,3]
  [3]

8 subsets, expected 2^3 = 8

by bitmask, no recursion at all:
  000 -> []
  001 -> [1]
  010 -> [2]
  011 -> [1,2]
  100 -> [3]
  101 -> [1,3]
  110 -> [2,3]
  111 -> [1,2,3]

有两个细节缺一不可。

all.Add([.. current]) 做了拷贝。 current 是同一个列表，一直在被修改。如果只存它的引用，all 里的每一项最后都指向同一个对象——而到最后，这个对象是空的。集合表达式里的展开就是这次拷贝。

每个节点都要记录，而不只是叶子。 子集不是“一条走到底的完整路径”，而是树上的任意节点。所以 all.Add 放在循环之前，而不是放在基准情况里。

最后的位掩码版本是不用递归的同一种枚举，和第 9 篇的模式 45 呼应。单就子集而言，它通常是更好的答案——没有栈，不用撤销，每一位就是选或不选的决定。

代价： O(2ⁿ) 个子集，全部输出要 O(n · 2ⁿ)。

适用场景： 题目要求所有子集、幂集，或者任意大小的所有组合。

模式 72 — 排列

求所有排列顺序。一共 n! 个，所以只在 n 很小时才可行。

最直接的实现是维护一个 used[] 数组，每个分支新建一个列表。交换版本两样都不需要。

int[] a = [1, 2, 3];
List<string> all = [];

// Swap the chosen element into position, recurse on the rest, swap it back.
// No "used" array, no allocation per branch.
void Permute(int k, int depth)
{
    if (k == a.Length)
    {
        all.Add(string.Join(",", a));
        Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", a)}]  <- complete");
        return;
    }

    for (int i = k; i < a.Length; i++)
    {
        (a[k], a[i]) = (a[i], a[k]);            // choose: a[i] goes to position k
        Console.WriteLine($"{new string(' ', depth * 2)}position {k} := {a[k]}   array now [{string.Join(",", a)}]");
        Permute(k + 1, depth + 1);
        (a[k], a[i]) = (a[i], a[k]);            // un-choose: put it back
    }
}

Permute(0, 0);
Console.WriteLine($"\n{all.Count} permutations, expected {a.Length}! = {Enumerable.Range(1, a.Length).Aggregate(1, (x, y) => x * y)}");
Console.WriteLine($"array restored to its original order: [{string.Join(",", a)}]");

输出：

position 0 := 1   array now [1,2,3]
  position 1 := 2   array now [1,2,3]
    position 2 := 3   array now [1,2,3]
      [1,2,3]  <- complete
  position 1 := 3   array now [1,3,2]
    position 2 := 2   array now [1,3,2]
      [1,3,2]  <- complete
position 0 := 2   array now [2,1,3]
  position 1 := 1   array now [2,1,3]
    position 2 := 3   array now [2,1,3]
      [2,1,3]  <- complete
  position 1 := 3   array now [2,3,1]
    position 2 := 1   array now [2,3,1]
      [2,3,1]  <- complete
position 0 := 3   array now [3,2,1]
  position 1 := 2   array now [3,2,1]
    position 2 := 1   array now [3,2,1]
      [3,2,1]  <- complete
  position 1 := 1   array now [3,1,2]
    position 2 := 2   array now [3,1,2]
      [3,1,2]  <- complete

6 permutations, expected 3! = 6
array restored to its original order: [1,2,3]

把选中的元素交换到位置 k，对 k+1 递归，再换回来。位置 k 已经定下；从 k 往后的元素都还可以用，只是顺序不定。

输出的最后一行是值得保留的检查：整个过程结束后，数组恢复成原来的顺序。如果没有恢复，就说明某处漏了撤销选择——这比在几百个排列里找出一个错的要容易发现得多。

交换版本产生的排列不是字典序，输出里能看出来。如果题目要求有序输出，要么事后排序，要么用 used[] 版本。

代价： O(n!) 个结果，O(n) 额外空间。

适用场景： 题目关于排列顺序、摆放方式，或者生成变位词。

模式 73 — 剪枝

单纯的回溯就是穷举搜索。剪枝才让它真正能用，真正的收益也都在这里。

int[] candidates = [2, 3, 6, 7];
int target = 7;

Array.Sort(candidates);          // sorting is what makes the pruning possible
List<List<int>> found = [];
List<int> current = [];
int calls = 0, pruned = 0;

void Search(int start, int remaining, int depth)
{
    calls++;
    if (remaining == 0)
    {
        found.Add([.. current]);
        Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", current)}]  <- sums to {target}");
        return;
    }

    for (int i = start; i < candidates.Length; i++)
    {
        if (candidates[i] > remaining)
        {
            // Sorted, so every candidate after this one is bigger too.
            pruned += candidates.Length - i;
            Console.WriteLine($"{new string(' ', depth * 2)}{candidates[i]} > {remaining}, and the rest are larger -> prune {candidates.Length - i} branches");
            break;
        }
        current.Add(candidates[i]);
        Search(i, remaining - candidates[i], depth + 1);   // i, not i+1: reuse allowed
        current.RemoveAt(current.Count - 1);
    }
}

Search(0, target, 0);
Console.WriteLine($"\nsolutions: {string.Join("  ", found.Select(f => "[" + string.Join(",", f) + "]"))}");
Console.WriteLine($"recursive calls: {calls}, branches pruned: {pruned}");
Console.WriteLine($"\nSearch(i, ...) rather than Search(i + 1, ...) lets a candidate repeat.");
Console.WriteLine($"Starting at i rather than 0 is what stops [2,2,3] and [2,3,2] both appearing.");

输出：

      2 > 1, and the rest are larger -> prune 4 branches
      [2,2,3]  <- sums to 7
    6 > 3, and the rest are larger -> prune 2 branches
    3 > 2, and the rest are larger -> prune 3 branches
  6 > 5, and the rest are larger -> prune 2 branches
    3 > 1, and the rest are larger -> prune 3 branches
  6 > 4, and the rest are larger -> prune 2 branches
  6 > 1, and the rest are larger -> prune 2 branches
  [7]  <- sums to 7

solutions: [2,2,3]  [7]
recursive calls: 10, branches pruned: 18

Search(i, ...) rather than Search(i + 1, ...) lets a candidate repeat.
Starting at i rather than 0 is what stops [2,2,3] and [2,3,2] both appearing.

先给候选数排序，剪枝才成为可能。一旦 candidates[i] > remaining，后面每个候选数都更大，所以整个剩余循环都可以用 break 放弃，而不是 continue。输入只有四个数，就有十八个分支根本没被探索。

两个下标细节，而且彼此不同：

• 用 Search(i, ...) 而不是 Search(i + 1, ...)，候选数才能重复使用，[2,2,3] 在这里才合法。
• 循环从 start 开始而不是从 0 开始，才能避免 [2,2,3] 和 [2,3,2] 同时出现。组合是无序的；这里只生成非递减序列。

代价： 最坏情况下是指数级，实际往往好得多。剪枝本身就是算法。

适用场景： 问题形态是穷举搜索，但完整的搜索树太大——组合总和、划分、约束类问题。

模式 74 — 输入里有重复

给定 [1, 2, 2]，每个不同的子集只输出一次。

int[] a = [1, 2, 2];
Array.Sort(a);                    // duplicates must be ADJACENT for the skip to work

static List<string> Subsets(int[] a, bool skipDuplicates)
{
    List<string> all = [];
    List<int> current = [];

    void Explore(int start)
    {
        all.Add("[" + string.Join(",", current) + "]");
        for (int i = start; i < a.Length; i++)
        {
            // At this level, a repeated value would rebuild a branch already done.
            // i > start is the key: the FIRST 2 at a level is fine, the second is not.
            if (skipDuplicates && i > start && a[i] == a[i - 1]) continue;
            current.Add(a[i]);
            Explore(i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }
    Explore(0);
    return all;
}

var naive = Subsets(a, false);
var fixed_ = Subsets(a, true);

Console.WriteLine($"input: [{string.Join(",", a)}]\n");
Console.WriteLine($"without the skip: {string.Join(" ", naive)}");
Console.WriteLine($"  {naive.Count} results, {naive.Distinct().Count()} of them distinct");
Console.WriteLine($"  repeated: {string.Join(" ", naive.GroupBy(x => x).Where(g => g.Count() > 1).Select(g => g.Key))}");

Console.WriteLine($"\nwith the skip:    {string.Join(" ", fixed_)}");
Console.WriteLine($"  {fixed_.Count} results, {fixed_.Distinct().Count()} of them distinct");

Console.WriteLine($"\ni > start, not i > 0. Using the second 2 as the FIRST pick at a level");
Console.WriteLine($"is a new branch; using it as a LATER pick repeats one already taken.");
Console.WriteLine($"That is a different bug from part 1's duplicate anchors, and it needs");
Console.WriteLine($"its own condition.");

输出：

input: [1,2,2]

without the skip: [] [1] [1,2] [1,2,2] [1,2] [2] [2,2] [2]
  8 results, 6 of them distinct
  repeated: [1,2] [2]

with the skip:    [] [1] [1,2] [1,2,2] [2] [2,2]
  6 results, 6 of them distinct

i > start, not i > 0. Using the second 2 as the FIRST pick at a level
is a new branch; using it as a LATER pick repeats one already taken.
That is a different bug from part 1's duplicate anchors, and it needs
its own condition.

不跳过的话：八个结果，只有六个不同，[1,2] 和 [2] 各出现两次。

修复办法是在排好序的数组上加 if (i > start && a[i] == a[i - 1]) continue;。关键全在这个条件上，而且比较的对象是 start，不是零：

• 在同一层，选第二个 2 会重建第一个 2 已经建过的分支。跳过它。
• 更深一层时，start 已经越过第一个 2，此时 i == start，第二个 2 是这一层的第一个选择——得到的是真正的新子集。允许它。[2,2] 就是这样保留下来的。

第 1 篇的 3Sum 也有重复问题，但那是另一种——在双指针扫描中跳过重复的锚点。名字一样，bug 不同，修法也不同。两个条件谁也帮不了谁。

适用场景： 输入可能有重复，而输出不能有。

模式 75 — N 皇后

在 n × n 的棋盘上放 n 个皇后，让它们互不攻击。

int n = 4;
int[] col = new int[n];        // col[r] = which column the queen in row r sits in
List<string[]> solutions = [];
int placed = 0, rejected = 0;

bool Safe(int row, int c)
{
    for (int r = 0; r < row; r++)
    {
        if (col[r] == c) return false;                       // same column
        if (Math.Abs(col[r] - c) == row - r) return false;    // same diagonal
    }
    return true;
}

void Place(int row)
{
    if (row == n)
    {
        solutions.Add([.. Enumerable.Range(0, n).Select(r => new string('.', col[r]) + "Q" + new string('.', n - col[r] - 1))]);
        Console.WriteLine($"  solution: columns {string.Join(",", col)}");
        return;
    }

    for (int c = 0; c < n; c++)
    {
        if (!Safe(row, c)) { rejected++; continue; }
        col[row] = c;                 // choose
        placed++;
        Place(row + 1);               // explore
        // un-choose is implicit: col[row] is overwritten next iteration and
        // never read for rows >= the current one.
    }
}

Console.WriteLine($"{n}-queens:");
Place(0);

Console.WriteLine($"\n{solutions.Count} solutions");
foreach (var s in solutions)
{
    Console.WriteLine();
    foreach (string row in s) Console.WriteLine($"  {row}");
}

Console.WriteLine($"\nplacements tried: {placed}, rejected by Safe: {rejected}");
Console.WriteLine($"brute force would test {Math.Pow(n, n):N0} arrangements");
Console.WriteLine();
Console.WriteLine("One queen per row is built into the shape of the recursion, so that");
Console.WriteLine("constraint never has to be checked. Only columns and diagonals are.");

输出：

4-queens:
  solution: columns 1,3,0,2
  solution: columns 2,0,3,1

2 solutions

  .Q..
  ...Q
  Q...
  ..Q.

  ..Q.
  Q...
  ...Q
  .Q..

placements tried: 16, rejected by Safe: 44
brute force would test 256 arrangements

One queen per row is built into the shape of the recursion, so that
constraint never has to be checked. Only columns and diagonals are.

这里最值得带走的设计是：“每行一个皇后”已经内建在递归的结构里。 Place(row + 1) 意味着每次调用恰好负责一行，所以“没有两个皇后同行”天然成立，从来不用检查。

状态也因此变小了。棋盘不是 n × n 的网格，而是一个 int[n]——col[r] 就是第 r 行皇后所在的列。只剩两项检查：同一列，以及同一对角线，也就是 Math.Abs(col[r] - c) == row - r。

这里没有显式的撤销选择，注释说明了原因：col[row] 在下一轮迭代时会被覆盖，而当前行及以下的位置之后再也不会被读取。撤销选择什么都不用做时，值得写一行注释说明——不然下一个读代码的人会以为是忘了写。

代价： 远好于暴力法要测试的 256 种摆法，但仍然是指数级。

适用场景： 问题是约束类谜题——数独、单词搜索、图着色。把约束编码进递归的结构，而不是逐个检查，每次都值得往这个方向想。

要点

• 选择、探索、撤销选择。 大家漏掉的是撤销选择，而少了它，代码看起来照样完整。
• 记录状态时要拷贝。 [.. current]——否则每个结果都指向同一个列表，而它最后是空的。
• 子集在每个节点都记录，而不只在叶子。 Add 放在循环之前。
• 检查状态最后是否恢复。 排列数组回到原始顺序，就证明撤销和选择一一对应。
• 先排序再剪枝，用 break 而不是 continue。 在有序列表上，一个候选数太大，后面的就都太大。
• i 让候选数可以重复使用；start 防止顺序不同的重复组合。 这是两个不同的下标决定，很容易混为一谈。
• 去重的条件是 i > start，不是 i > 0。 和 start 比较，同一个值在更深一层仍然可以作为第一个选择。
• 能把约束编码进递归结构时，就这样做。 每次调用负责一行，行规则就一行代码都不需要。

第 16 篇是最后一篇：位运算。这个系列从第 3 篇起就一直在用它，只是从没明说。