How it works
Backtracking explores a choice, solves the remaining smaller problem, and then restores state before trying the next choice. For permutations, each depth chooses one unused symbol for the next buffer position. Reaching the buffer length means every position has been assigned, so one complete permutation is ready.
The sample produces six arrangements of three distinct symbols. The used array tracks which input positions belong to the current partial arrangement. Resetting used[index] after the recursive call is essential: without that restoration, later branches would incorrectly believe symbols remained occupied by earlier completed choices.
At a leaf, new string(buffer) copies the current character contents into an immutable result. Storing the mutable buffer object itself would make every recorded result share one changing array. This ownership detail is just as important as the recursion, because a correct search can still produce corrupted saved output through accidental shared state.
The number of permutations grows factorially for distinct symbols. A small runnable example is not evidence that exhaustive enumeration is practical for a large input. If a caller only needs to find one arrangement satisfying a condition, introduce pruning or early termination with a clearly defined contract.
Practice with zero, one, and four distinct symbols. Explain why the empty input has one empty arrangement in this implementation. Then introduce repeated characters and observe duplicate strings: the algorithm chooses input positions, so equal values at different positions still create distinct search branches.
Finally, decide whether a reusable API requires distinct input values, duplicate-free output, or position-distinct results. Those are different contracts. Test both state restoration and result ownership, and keep the final sorting step separate from generation so deterministic display order is not confused with the traversal's core correctness.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
char[] symbols = { 'A', 'B', 'C' };
var used = new bool[symbols.Length];
var buffer = new char[symbols.Length];
var results = new List<string>();
Search(0);
Console.WriteLine(results.Count);
Console.WriteLine(string.Join(",", results.OrderBy(value => value, StringComparer.Ordinal)));
void Search(int depth) {
if (depth == symbols.Length) { results.Add(new string(buffer)); return; }
for (int index = 0; index < symbols.Length; index++) {
if (used[index]) continue;
used[index] = true; buffer[depth] = symbols[index];
Search(depth + 1);
used[index] = false;
}
}
Expected output
6 ABC,ACB,BAC,BCA,CAB,CBA
Undo the used marker after returning so the next branch starts from the correct state.