Backtracking in C#: Subsets, Permutations and N-Queens

Backtracking is the pattern with the smallest core and the widest reach. Every problem here is the same three lines with a different branching rule.

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

Part 13’s root-to-leaf paths already used it. This part is what it is for.

Every program below is complete, was run on .NET 10, and its output is pasted from the run.

Pattern 71 — Subsets

Every subset of a set. For each element there are two choices, so the search is a binary tree n levels deep.

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)}]");
}

It prints:

[]
  [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]

Two details are load-bearing.

all.Add([.. current]) copies. current is one list that keeps being mutated, so storing a reference to it means every entry in all ends up pointing at the same object — and at the end that object is empty. The collection-expression spread is the copy.

Recording happens at every node, not at the leaves. A subset is not “a complete path to the bottom”, it is any node in the tree, which is why all.Add is before the loop rather than inside a base case.

The bitmask version at the end is the same enumeration without recursion, and it connects to pattern 45 in part 9. For subsets specifically it is usually the better answer — no stack, no undo, and the bits are the include/exclude decisions.

Cost: O(2ⁿ) subsets, O(n · 2ⁿ) to write them all out.

Reach for it when the problem asks for all subsets, the power set, or all combinations of any size.

Pattern 72 — Permutations

Every ordering. n! of them, so this is only ever viable for small n.

The obvious implementation keeps a used[] array and builds a fresh list per branch. The swap version needs neither.

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)}]");

It prints:

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]

Swap the chosen element into position k, recurse on k+1, then swap it back. Position k has been decided; everything from k onwards is still available, in some order.

The last line of that output is the check worth keeping: the array is back in its original order when the whole thing finishes. If it is not, an un-choose is missing somewhere — and that is a much easier thing to spot than a wrong permutation buried in a list of hundreds.

The swap version does not produce permutations in lexicographic order, which the output shows. If the problem wants sorted output, either sort afterwards or use the used[] version.

Cost: O(n!) results, O(n) extra space.

Reach for it when the problem is about orderings, arrangements, or anagram generation.

Pattern 73 — Pruning

Backtracking on its own is exhaustive search. Pruning is what makes it usable, and it is where the real gains are.

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.");

It prints:

      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.

Sorting the candidates first is what makes pruning possible. Once candidates[i] > remaining, every later candidate is bigger too, so the whole rest of the loop can be abandoned with break rather than continue. Eighteen branches never explored, on an input of four numbers.

Two index details, and they are different from each other:

• Search(i, ...) rather than Search(i + 1, ...) lets a candidate be reused, which is what makes [2,2,3] legal here.
• Starting the loop at start rather than 0 is what stops [2,2,3] and [2,3,2] both being reported. Combinations are unordered; only non-decreasing sequences are generated.

Cost: exponential in the worst case, and often far better. The pruning is the algorithm.

Reach for it when exhaustive search is the shape but the full tree is too big — combination sum, partitioning, constraint problems.

Pattern 74 — Duplicates in the input

Given [1, 2, 2], report each distinct subset once.

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.");

It prints:

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.

Without the skip: eight results, six distinct, with [1,2] and [2] each appearing twice.

The fix is if (i > start && a[i] == a[i - 1]) continue; on a sorted array. The condition is the whole thing, and the comparison is against start, not zero:

• At one level, picking the second 2 rebuilds a branch the first 2 already built. Skip it.
• Deeper down, where start has moved past the first 2, i == start and the second 2 is the first pick at that level — a genuinely new subset. Allow it. That is how [2,2] survives.

Part 1’s 3Sum had a duplicate problem too, and it was a different one — skipping repeated anchors in a two-pointer scan. Same word, different bug, different fix. Neither condition helps with the other.

Reach for it when the input may contain repeats and the output must not.

Pattern 75 — N-Queens

Place n queens on an n × n board so that none attack each other.

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.");

It prints:

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.

The design choice worth taking away is that one queen per row is built into the shape of the recursion. Place(row + 1) means each call owns exactly one row, so “no two queens share a row” is true by construction and is never tested.

That also collapses the state. The board is not an n × n grid but an int[n] — col[r] is where the queen in row r sits. Only two checks remain: same column, and same diagonal, which is Math.Abs(col[r] - c) == row - r.

There is no explicit un-choose, and the comment says why: col[row] is overwritten on the next iteration, and nothing at or below the current row is ever read again. When the un-choose is a no-op it is worth a comment saying so — otherwise the next reader assumes it was forgotten.

Cost: far better than the 256 arrangements brute force would test, and still exponential.

Reach for it when the problem is a constraint puzzle — Sudoku, word search, graph colouring. Encoding a constraint into the recursion’s shape rather than testing for it is the move to look for every time.

What to remember

• Choose, explore, un-choose. The un-choose is the one people leave out, and the code looks complete without it.

• Copy the state when you record it. [.. current] — otherwise every result points at one list that ends up empty.

• Subsets are recorded at every node, not at the leaves. The Add goes before the loop.

• Check that the state is restored at the end. A permutation array back in its original order proves the undos balanced.

• Sort before you prune, and break rather than continue. Once one candidate is too big, on a sorted list they all are.

• i reuses a candidate; start prevents reordered duplicates. Two different index decisions that are easy to conflate.

• The duplicate skip is i > start, not i > 0. Against start, so the same value can still be the first pick at a deeper level.

• Build constraints into the recursion’s shape when you can. One row per call means the row rule needs no code at all.

Part 16 is the last one: bit manipulation, which the series has been using since part 3 without ever saying so out loud.