Build a candidate one choice at a time. When it cannot lead anywhere, undo the last choice and try the next. The undo is the whole pattern.
Backtracking is depth-first search over a tree of decisions rather than a tree of nodes. The output is exponential by nature, so the goal is never to avoid the exponential. It is to cut off whole branches as early as possible, and to enumerate each answer exactly once.
n ≤ 20 for subsets, n ≤ 10 for permutations. A small bound is a hint that exponential is expected.Before writing any backtracking code, answer these three out loud. They determine every line.
for loop iterates over: an index, a value, a column, a letter.start index for combinations, a used array for permutations, and a skip rule if the input itself has repeats.[1, 2] and [2, 1] are the same answer, and a start index enforces one canonical ordering. Permutations are ordered, so both are wanted, and instead you need a used marker so no element is picked twice within one arrangement. Choosing the wrong guard gives you either duplicates or missing answers.n. Interviewers ask about it, and “there are 2ⁿ answers and copying each one costs O(n)” is the whole explanation./// <summary>
/// The universal backtracking skeleton. Each placeholder is an abstract method, so a
/// problem fills in only the parts that differ. The search loop never changes.
/// </summary>
/// <typeparam name="TState">What a call needs to know. Subsets: the start index.</typeparam>
/// <typeparam name="TOption">One choice. Subsets: a value. N-Queens: a column.</typeparam>
public abstract class Backtracker<TState, TOption>
{
// Every finished answer, each its own copy.
private readonly List<List<TOption>> results = [];
// The choices made on the current path, root to here.
private readonly List<TOption> trail = [];
/// <summary>The choices on the current path. Read-only for subclasses.</summary>
protected IReadOnlyList<TOption> Trail => trail;
// initialState: the root of the tree, nothing chosen yet.
// Subsets: start = 0. Combination Sum: (start 0, remaining = target). N-Queens: row 0.
protected abstract TState InitialState();
// isComplete(state): is the trail a finished answer?
// Permutations: Trail.Count == nums.Length. Combination Sum: remaining == 0.
protected abstract bool IsComplete(TState state);
// candidates(state): the options for the next decision.
// Subsets: nums[start..]. Permutations: all of nums. N-Queens: columns 0..n-1.
protected abstract IEnumerable<TOption> Candidates(TState state);
// isValid(option, state): may this option be taken here?
// Permutations: not used[i]. N-Queens: the square is not attacked.
protected abstract bool IsValid(TOption option, TState state);
// apply: record the choice in any side structures.
// Permutations: used[i] = true. N-Queens: add to the three sets.
protected abstract void Apply(TState state, TOption option);
// undo: the exact reverse of Apply, so the loop invariant holds.
protected abstract void Undo(TState state, TOption option);
// advance(state, option): the state one level deeper.
// Subsets: start becomes i + 1. Combination Sum: remaining drops by option.
protected abstract TState Advance(TState state, TOption option);
/// <summary>Enumerate every valid arrangement.</summary>
/// <returns>Each finished trail, copied, in depth-first order.</returns>
/// <example>A permutations subclass on [1, 2] returns [[1, 2], [2, 1]].</example>
public List<List<TOption>> Run()
{
results.Clear();
trail.Clear();
Explore(InitialState());
return results;
}
private void Explore(TState state)
{
if (IsComplete(state))
{
// [.. trail] copies. trail keeps changing, so adding trail itself
// would leave every result pointing at one list, empty at the end.
results.Add([.. trail]);
return;
}
// Invariant: trail and state are exactly as they were on entry.
foreach (TOption option in Candidates(state))
{
if (!IsValid(option, state))
{
continue; // prune this branch entirely
}
trail.Add(option); // choose
Apply(state, option);
Explore(Advance(state, option)); // recurse
Undo(state, option); // un-choose
// Count - 1: the last slot, which holds the option we just tried.
trail.RemoveAt(trail.Count - 1);
}
}
}
Every problem below is this skeleton with different answers to the three questions. The continue is where pruning lives, and pruning is the only lever you have on the running time. In C# the placeholders become abstract methods, so the skeleton really compiles. Two C# details matter. [.. trail] is a collection expression that copies the list. trail.RemoveAt(trail.Count - 1) is the pop, and it is O(1) because it removes the last slot. In an interview you would write one method with local functions, as the problems below do.
Here is the skeleton filled in for permutations. Each override is one answer to the three questions:
/// <summary>Permutations as a filled-in Backtracker. Options are the values.</summary>
/// <example><c>new PermutationsViaTemplate([1, 2]).Run()</c> returns [[1, 2], [2, 1]].</example>
public sealed class PermutationsViaTemplate(int[] nums) : Backtracker<int, int>
{
// Values already on the trail. The values are distinct, so a set is enough.
private readonly HashSet<int> used = [];
// State = depth, the number of values placed. The root has placed 0.
protected override int InitialState() => 0;
// Full length: every value is placed.
protected override bool IsComplete(int depth) => depth == nums.Length;
// Every position may draw from the whole array, so there is no start index.
protected override IEnumerable<int> Candidates(int depth) => nums;
// A value may appear only once per arrangement.
protected override bool IsValid(int value, int depth) => !used.Contains(value);
protected override void Apply(int depth, int value) => used.Add(value);
protected override void Undo(int depth, int value) => used.Remove(value);
// + 1: one more position is filled.
protected override int Advance(int depth, int value) => depth + 1;
}
trail list. Choose pushes, un-choose pops, so the list always matches the current path.Reading the figure. Each column is a moment in time, left to right. Blue boxes sit in trail. Amber is the value just pushed. The red dashed box is the value just popped. Notice that frame 4 matches frame 2 exactly. That is the undo restoring the state before the next option.
trail instead of [.. trail]. List<int> is a reference type. Every result ends up being the same list object, empty at the end. The number one bug in this pattern. new List<int>(trail) and trail.ToList() also copy.start = i + 1 when reuse is allowed, or start = i when it is not. One character, completely different problem.n. Mutate and undo instead.foreach walks it. C# throws InvalidOperationException. Loop by index over a frozen count, as the iterative subsets version does.Array.Sort works in place. The solutions here sort a copy, int[] sorted = [.. nums], so the input is left alone.Given an array of distinct integers, return all possible subsets, the power set. The answer must not contain duplicate subsets.
start index. By only ever extending with a later index, each subset is generated in exactly one order.public static class Subsets
{
/// <summary>Every subset of an array of distinct integers.</summary>
/// <param name="nums">Distinct integers.</param>
/// <returns>All 2^n subsets, including the empty one, in depth-first order.</returns>
/// <example>
/// <c>All([1, 2, 3])</c> returns
/// [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].
/// </example>
public static List<List<int>> All(int[] nums)
{
var results = new List<List<int>>(); // every subset found so far
var trail = new List<int>(); // the subset being built on this path
// start: the first index this level may pick. Only later indices are
// allowed, so each subset is built in one order: increasing index.
void Build(int start)
{
// Every node in the tree is a complete answer, so record on entry.
// [.. trail] copies, because trail keeps changing after this.
results.Add([.. trail]);
// i: the index added at this level. Invariant: trail is the same
// at the top of every pass, because each pass undoes its own choice.
for (int i = start; i < nums.Length; i++)
{
trail.Add(nums[i]); // choose
Build(i + 1); // i + 1: never reuse or go backwards
trail.RemoveAt(trail.Count - 1); // un-choose: Count - 1 is the last slot
}
}
Build(0); // 0: the root may pick any index
return results;
}
}
Subsets.All([1, 2, 3]) records a subset on every call, so the output order is the depth-first visit order.Reading the figure. Each box is one call to build, and #1 to #8 is the order it records. Height is trail.Count. A solid blue step is one push. A red dashed step pops twice, then pushes the next index. The list matches the <example> and the tests exactly: [ ], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3].
public static class SubsetsIterative
{
/// <summary>
/// Double the answer set for each new element. Every old subset stays, and every
/// old subset plus the new element joins. That doubling is why there are 2^n.
/// </summary>
/// <param name="nums">Distinct integers.</param>
/// <returns>All 2^n subsets.</returns>
/// <example><c>All([1, 2])</c> returns [[], [1], [2], [1, 2]].</example>
public static List<List<int>> All(int[] nums)
{
// [[]]: the power set of nothing holds one subset, the empty one.
List<List<int>> results = [[]];
// Invariant: results is the power set of the values seen so far.
foreach (int value in nums)
{
// Freeze the count first. C# throws if you add to a List while a
// foreach walks it, and we only want the OLD subsets here.
int oldCount = results.Count;
// k walks the old subsets, 0 up to oldCount - 1.
for (int k = 0; k < oldCount; k++)
{
// A copy of the old subset with value appended.
results.Add([.. results[k], value]);
}
}
return results;
}
}
A short loop, and it makes the 2ⁿ count obvious. Show the backtracking version first, because the interviewer wants to see the pattern, then offer this.
public static class SubsetsBitmask
{
/// <summary>Each integer from 0 to 2^n - 1 is a membership mask.</summary>
/// <param name="nums">Distinct integers, at most 30 of them.</param>
/// <returns>All 2^n subsets, ordered by mask.</returns>
/// <example><c>All([1, 2])</c> returns [[], [1], [2], [1, 2]].</example>
public static List<List<int>> All(int[] nums)
{
int n = nums.Length;
var results = new List<List<int>>();
// 1 << n is 2^n, so mask runs 0..2^n - 1: one mask per subset.
// An int has 31 value bits, so 1 << 31 goes negative. Fine for n <= 30.
for (int mask = 0; mask < 1 << n; mask++)
{
var subset = new List<int>();
// i: which bit, and so which element, is being tested.
for (int i = 0; i < n; i++)
{
// (mask >> i) & 1: shift bit i to the bottom, keep only that bit.
// 1 means nums[i] is in this subset, 0 means it is out.
if (((mask >> i) & 1) == 1)
{
subset.Add(nums[i]);
}
}
results.Add(subset);
}
return results;
}
}
The bitmask version stops at n = 30, because 1 << 31 overflows an int. Use 1L << n and a long mask to go further, though the output would not fit in memory anyway.
public static class SubsetsWithDup
{
/// <summary>Subsets of an array that may repeat values, with no duplicate subsets.</summary>
/// <param name="nums">Integers, possibly repeated. Not modified.</param>
/// <returns>Each distinct subset once, built from sorted values.</returns>
/// <example>
/// <c>All([1, 2, 2])</c> returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
/// </example>
public static List<List<int>> All(int[] nums)
{
// Sort a copy so equal values sit side by side. The caller's array is untouched.
int[] sorted = [.. nums];
Array.Sort(sorted);
var results = new List<List<int>>(); // every distinct subset found so far
var trail = new List<int>(); // the subset being built on this path
void Build(int start)
{
results.Add([.. trail]); // every node is an answer, so copy it now
// i: the index added at this level. Invariant: trail is unchanged
// at the top of every pass.
for (int i = start; i < sorted.Length; i++)
{
// Skip a repeat at the same tree level. The first copy already
// generated every subset this branch could produce.
// i > start: not the first option at this level.
// i - 1: the neighbour to the left, equal values sit side by side.
if (i > start && sorted[i] == sorted[i - 1])
{
continue;
}
trail.Add(sorted[i]); // choose
Build(i + 1); // i + 1: only later indices, no reuse
trail.RemoveAt(trail.Count - 1); // un-choose: Count - 1 is the last slot
}
}
Build(0); // 0: the root may pick any index
return results;
}
}
i > start and not i > 0. The rule is “do not pick the same value twice as the same decision”. Picking a repeated value at a deeper level is legitimate, that is how [2, 2] gets built. i > start says “this is not the first option I am trying at this level”, which is exactly the right condition. This idiom reappears in every duplicate-tolerant backtracking problem.[[]], a list containing the empty subset, not an empty list.[[], [x]].n = 20 gives about a million subsets, which is fine. n = 30 gives a billion, which is not. Say where the ceiling is.n, so the 1 MB stack is never the limit here. Memory for the output is.start index is what makes each subset appear exactly once.”Given an array of distinct integers, return all possible permutations.
start index.used array, because the constraint is “each element once per arrangement”, not “increasing order”. Order matters here, so a start index would wrongly discard most answers.public static class Permutations
{
/// <summary>Every ordering of an array of distinct integers.</summary>
/// <param name="nums">Distinct integers.</param>
/// <returns>All n! permutations, in lexicographic order of index.</returns>
/// <example>
/// <c>All([1, 2, 3])</c> returns
/// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
/// </example>
public static List<List<int>> All(int[] nums)
{
var results = new List<List<int>>(); // every full arrangement found
var trail = new List<int>(); // the arrangement built so far
// used[i]: nums[i] is in trail. new bool[] starts all false: all free.
var used = new bool[nums.Length];
void Build()
{
// Full length means every element is placed: one finished permutation.
if (trail.Count == nums.Length)
{
results.Add([.. trail]); // copy, because trail keeps changing
return;
}
// i: the candidate for the next position. Every index is tried, so no start.
// Invariant: trail and used are the same at the top of every pass.
for (int i = 0; i < nums.Length; i++)
{
if (used[i])
{
continue; // already placed in this arrangement
}
used[i] = true; // choose
trail.Add(nums[i]);
Build(); // fill the remaining positions
trail.RemoveAt(trail.Count - 1); // un-choose, both parts
used[i] = false;
}
}
Build();
return results;
}
}
public static class PermuteSwap
{
/// <summary>No used array: swap each candidate into position, then swap it back.</summary>
/// <param name="input">Distinct integers. Not modified.</param>
/// <returns>All n! permutations, not in lexicographic order.</returns>
/// <example><c>All([1, 2])</c> returns [[1, 2], [2, 1]].</example>
public static List<List<int>> All(int[] input)
{
int[] nums = [.. input]; // work on a copy, keep the input intact
var results = new List<List<int>>(); // every arrangement found
// first: the position being filled. nums[..first] is fixed, nums[first..]
// holds the elements still free to go here.
void Build(int first)
{
// Every position is fixed, so nums itself is one permutation.
if (first == nums.Length)
{
results.Add([.. nums]); // copy, because nums keeps changing
return;
}
// i: which free element moves into position first.
// Invariant: nums is in the same order at the top of every pass.
for (int i = first; i < nums.Length; i++)
{
(nums[first], nums[i]) = (nums[i], nums[first]); // choose
Build(first + 1); // + 1: fill the next position
(nums[first], nums[i]) = (nums[i], nums[first]); // un-choose
}
}
Build(0); // 0: start filling at the first position
return results;
}
}
Uses O(1) extra space beyond the recursion, and it is a nice thing to show. The cost is that the output order is no longer lexicographic, so mention that if the problem cares.
For [1, 2, 3]: the first level tries 1, 2, 3. Inside the 1 branch, the second level tries 2 and 3, since 1 is marked used. Inside 1, 2 only 3 is free, so the trail reaches full length and [1, 2, 3] is recorded. Unwinding un-marks 3, then 2, and the 1 branch tries 3 next.
Permutations.All([1, 2, 3]). Every level may pick any unused value, so the tree fans out 3, then 2, then 1.Reading the figure. Blue boxes are partial trails, which are not recorded. Green boxes are full-length trails, the six answers. The amber path is the first one the walkthrough follows. The muted used labels show why the [1] branch offers only 2 and 3. Compare with Figure 10.1. There is no start index here, so [2,1] appears as well as [1,2].
public static class PermuteUnique
{
/// <summary>Distinct permutations of an array that may contain repeats.</summary>
/// <param name="nums">Integers, possibly repeated. Not modified.</param>
/// <returns>Each distinct ordering once.</returns>
/// <example><c>All([1, 1, 2])</c> returns [[1, 1, 2], [1, 2, 1], [2, 1, 1]].</example>
public static List<List<int>> All(int[] nums)
{
int[] sorted = [.. nums]; // copy, then sort: equal values adjacent
Array.Sort(sorted);
var results = new List<List<int>>(); // every distinct arrangement found
var trail = new List<int>(); // the arrangement built so far
var used = new bool[sorted.Length]; // used[i]: sorted[i] is in trail. All false.
void Build()
{
if (trail.Count == sorted.Length) // every element placed
{
results.Add([.. trail]); // copy, because trail keeps changing
return;
}
// i: the candidate for the next position.
// Invariant: trail and used are the same at the top of every pass.
for (int i = 0; i < sorted.Length; i++)
{
if (used[i])
{
continue; // already placed in this arrangement
}
// Among equal values, only ever use them left to right. If the
// previous copy is unused, this branch mirrors one already explored.
// i > 0: index 0 has no left neighbour. i - 1: that left neighbour.
if (i > 0 && sorted[i] == sorted[i - 1] && !used[i - 1])
{
continue;
}
used[i] = true; // choose
trail.Add(sorted[i]);
Build(); // fill the remaining positions
trail.RemoveAt(trail.Count - 1); // un-choose, both parts
used[i] = false;
}
}
Build();
return results;
}
}
not used[i - 1] is subtle. It forces equal values to be consumed in index order, so exactly one of the interchangeable orderings survives. Write out [1, 1, 2] by hand once and it becomes clear. It is a common follow-up.[[]].[[x]].n = 10 is 3.6 million permutations, about the practical limit. n = 12 is half a billion.itertools. The manual version is what you would ship, so write it cleanly.start index here, because order matters and every position can draw from the whole array. The used array is what keeps each element to one appearance per arrangement.”Given an array of distinct positive integers candidates and a target, return all unique combinations that sum to the target. The same candidate may be used unlimited times. Two combinations are the same if they use the same multiset of numbers.
start index, but recursing with i rather than i + 1, because a candidate may be reused. That single character is the difference between this problem and Combination Sum II.candidates[i] > remaining, you can break rather than continue, because every later candidate is even larger and equally hopeless. That converts a per-item skip into cutting off the entire rest of the level, and it is the difference between a fast solution and a slow one on adversarial inputs.public static class CombinationSum
{
/// <summary>All multisets of candidates summing exactly to target, with reuse.</summary>
/// <param name="candidates">Distinct positive integers. Not modified.</param>
/// <param name="target">The required total, positive.</param>
/// <returns>Each qualifying combination once, in non-decreasing order.</returns>
/// <example><c>Find([2, 3, 6, 7], 7)</c> returns [[2, 2, 3], [7]].</example>
public static List<List<int>> Find(int[] candidates, int target)
{
int[] sorted = [.. candidates]; // copy, then sort: needed for the break
Array.Sort(sorted);
var results = new List<List<int>>(); // every combination that hits the target
var trail = new List<int>(); // the numbers chosen on this path
// start: the smallest index this level may pick, so trail stays
// non-decreasing. remaining: target minus the sum of trail.
void Build(int start, int remaining)
{
// 0 left means trail sums to exactly target: record a copy.
if (remaining == 0)
{
results.Add([.. trail]);
return;
}
// i: the candidate added at this level.
// Invariant: trail and remaining are unchanged at the top of every pass.
for (int i = start; i < sorted.Length; i++)
{
if (sorted[i] > remaining)
{
break; // sorted, so every later candidate overshoots
}
trail.Add(sorted[i]); // choose
Build(i, remaining - sorted[i]); // i, not i + 1: reuse is allowed
trail.RemoveAt(trail.Count - 1); // un-choose: Count - 1 is the last slot
}
}
Build(0, target); // 0: any candidate may start. Nothing spent.
return results;
}
}
candidates = [2, 3, 6, 7], target = 7:
[2], remaining 5: keep going from index 0.[2, 2], remaining 3: keep going.[2, 2, 2], remaining 1: 2 > 1, break, dead end.[2, 2, 3], remaining 0: record.[2, 3], remaining 2: start is 1, so 2 is unavailable. Dead end.[7], remaining 0: record.Note how [3, 2, 2] never appears: the start index prevents going back to a smaller candidate.
CombinationSum.Find([2, 3, 6, 7], 7) finds [2, 2, 3] and [7]. Sorting lets each dead level stop with one break.Reading the figure. Each box shows the trail and the remaining amount. Green boxes hit zero and are recorded. Red boxes are dead ends, and the red note says which test cut them off. Blue boxes keep searching. Children only use candidates at or after the parent’s index, so [3, 2, 2] is never built.
The recursion cannot go deeper than target / min(candidates), since each level subtracts at least the smallest candidate. That is the honest bound, and it explains why positivity is required.
public static class CombinationSumII
{
/// <summary>Each candidate may be used at most once, and the input may repeat.</summary>
/// <param name="candidates">Positive integers, possibly repeated. Not modified.</param>
/// <param name="target">The required total, positive.</param>
/// <returns>Each distinct combination once, in non-decreasing order.</returns>
/// <example>
/// <c>Find([10, 1, 2, 7, 6, 1, 5], 8)</c> returns [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].
/// </example>
public static List<List<int>> Find(int[] candidates, int target)
{
int[] sorted = [.. candidates]; // copy and sort: adjacent repeats, and the break
Array.Sort(sorted);
var results = new List<List<int>>(); // every combination that hits the target
var trail = new List<int>(); // the numbers chosen on this path
// start: the first index this level may pick. remaining: target minus sum(trail).
void Build(int start, int remaining)
{
if (remaining == 0) // exact hit: record a copy
{
results.Add([.. trail]);
return;
}
// i: the candidate added at this level.
// Invariant: trail and remaining are unchanged at the top of every pass.
for (int i = start; i < sorted.Length; i++)
{
if (sorted[i] > remaining)
{
break; // sorted: the rest overshoot too
}
// i > start: not the first option at this level.
// i - 1: the left neighbour, equal values sit side by side.
if (i > start && sorted[i] == sorted[i - 1])
{
continue; // same value, same level
}
trail.Add(sorted[i]); // choose
Build(i + 1, remaining - sorted[i]); // i + 1: no reuse
trail.RemoveAt(trail.Count - 1); // un-choose
}
}
Build(0, target); // 0: any candidate may start. Nothing spent.
return results;
}
}
Two changes from the first version: i + 1 instead of i, and the i > start duplicate skip. Being able to state both differences quickly is the point of studying them together.
[].remaining stops shrinking. Confirm the candidates are positive.target == 0: returns [[]]. Ask whether that is wanted.i rather than i + 1 is what allows reuse, and the start index is what stops the same multiset appearing in several orders. Sorting lets me break instead of continue.”Place n queens on an n × n board so that no two attack each other, and return every distinct solution as a list of board strings.
n. State this before writing anything. It is most of the insight.Scanning the board for conflicts is O(n) per placement. Three sets make it O(1):
col. Set: cols.row - col. Set: diagonals.row + col. Set: antiDiagonals.Every square on a given diagonal has the same row - col, and every square on an anti-diagonal has the same row + col. So a placement conflicts exactly when one of its three keys is already in a set. Deriving those two identities on the whiteboard is what this question is really testing.
public static class NQueens
{
/// <summary>Every arrangement of n non-attacking queens on an n by n board.</summary>
/// <param name="n">Board size, n >= 1.</param>
/// <returns>Each solution as n strings of "." and "Q".</returns>
/// <example>
/// <c>Solve(4)</c> returns
/// [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]].
/// </example>
public static List<List<string>> Solve(int n)
{
var results = new List<List<string>>(); // every finished board
var queenCol = new List<int>(); // queenCol[row] is that row's column
var cols = new HashSet<int>(); // columns that already hold a queen
var diagonals = new HashSet<int>(); // keyed by row - col
var antiDiagonals = new HashSet<int>(); // keyed by row + col
// Turn the column-per-row list into the required board strings.
// c dots, the queen, then the rest. n - c - 1: squares right of
// the queen, minus 1 for the queen's own square.
List<string> Render() =>
[.. queenCol.Select(c => new string('.', c) + "Q" + new string('.', n - c - 1))];
// row: the row to fill now. Rows 0..row-1 each hold one safe queen.
void Place(int row)
{
if (row == n) // rows 0..n-1 all filled: a full solution
{
results.Add(Render());
return;
}
// col: the column tried for this row, 0..n-1.
// Invariant: the three sets hold exactly the queens in rows 0..row-1.
for (int col = 0; col < n; col++)
{
// One queen per row is built in, so only columns and diagonals clash.
// row - col is constant on a down-right diagonal. row + col on an
// up-right one.
if (cols.Contains(col) || diagonals.Contains(row - col)
|| antiDiagonals.Contains(row + col))
{
continue; // prune: this square is attacked
}
cols.Add(col); // choose
diagonals.Add(row - col);
antiDiagonals.Add(row + col);
queenCol.Add(col);
Place(row + 1); // + 1: move on to the next row
queenCol.RemoveAt(queenCol.Count - 1); // un-choose, all four structures
antiDiagonals.Remove(row + col);
diagonals.Remove(row - col);
cols.Remove(col);
}
}
Place(0); // 0: start at the top row, board empty
return results;
}
}
NQueens.Solve(4) hits two dead ends, backs up to row 0, and then finds [".Q..", "...Q", "Q...", "..Q."].Reading the figure. Each board is one moment, left to right. Blue squares are queens already placed. Amber is the newest queen. A red x is a square in the row being tried that the three sets reject. When a whole row is red, place returns and the caller un-chooses. Green queens in (d) form the first answer, queenCol = [1, 3, 0, 2].
public static class NQueensCount
{
/// <summary>N-Queens II: just how many solutions, no boards.</summary>
/// <param name="n">Board size, n >= 1.</param>
/// <returns>The number of distinct solutions.</returns>
/// <example><c>Total(8)</c> returns 92.</example>
public static int Total(int n)
{
// bool arrays instead of HashSets: faster, and the keys are small integers.
var cols = new bool[n]; // n columns, 0..n-1
// 2 * n - 1 diagonals of each kind. row - col runs from -(n - 1) to n - 1,
// so + (n - 1) shifts it into 0..2n-2. row + col already runs 0..2n-2.
var diagonals = new bool[2 * n - 1];
var antiDiagonals = new bool[2 * n - 1];
// row: the row to fill now. Returns how many ways rows row..n-1 can finish.
int Place(int row)
{
if (row == n)
{
return 1; // all n rows filled: this path is 1 solution
}
int count = 0; // solutions found below this row so far
// col: the column tried for this row, 0..n-1.
// Invariant: the three arrays mark exactly the queens in rows 0..row-1.
for (int col = 0; col < n; col++)
{
int d = row - col + n - 1; // + n - 1: shift into 0..2n-2
int a = row + col;
if (cols[col] || diagonals[d] || antiDiagonals[a])
{
continue; // prune: this square is attacked
}
cols[col] = diagonals[d] = antiDiagonals[a] = true; // choose
count += Place(row + 1); // + 1: next row. Add its solution count.
cols[col] = diagonals[d] = antiDiagonals[a] = false; // un-choose
}
return count;
}
return Place(0); // 0: start at the top row, board empty
}
}
Same search, no rendering and no trail. Faster in practice because it never builds strings. It also swaps the three HashSet<int>s for bool arrays. The keys are small integers, so an array lookup is cheaper than a hash. The diagonal key row - col can be negative, so it is shifted by n - 1 to make it a valid index.
The bound is loose. Row 0 has n choices, row 1 has at most n - 2 after pruning, and so on, so the real search is far smaller than n!. Solution counts: 2 for n = 4, 10 for n = 5, 92 for n = 8.
n = 1: one solution, ["Q"].n = 2 and n = 3: no solutions, returns []. A good correctness check.n = 8: 92 solutions, the classic.row - col and an anti-diagonal has constant row + col, so three sets give me O(1) conflict checks.”start index for combinations (order does not matter). used array for permutations (order does matter).Build(i) allows reuse. Build(i + 1) does not. One character.i > start and x[i] == x[i - 1].[.. trail]. Pruning early, ideally with a break on sorted data, is the only real lever on running time.Pattern 11, Modified Binary Search, is the opposite instinct. Instead of exploring everything, it throws half the possibilities away at every step, and the skill is spotting the monotone boundary that licenses the throw.