Generate all string permutations
Generate every permutation of a string whose characters are distinct.
Course progress
Problem 48 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
text = "ABC"
Expected output
ABC ACB BAC BCA CBA CAB
What is happening?
Fix each character in the first position and recursively arrange the rest. Three distinct characters produce 3! = 6 permutations.
Solution strategy
Build the right mental model
Fix one position at a time by swapping each available character into it, recurse for the remaining positions, then undo the swap.
Core concepts
backtracking · recursion
Complexity
Time O(n x n!), call-stack space O(n), excluding the output.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for generate-permutations
using System;
using System.Collections.Generic;
class Program
{
static void Generate(char[] characters, int position, List<string> results)
{
if (position == characters.Length)
{
results.Add(new string(characters));
return;
}
for (int i = position; i < characters.Length; i++)
{
char temporary = characters[position];
characters[position] = characters[i];
characters[i] = temporary;
Generate(characters, position + 1, results);
temporary = characters[position];
characters[position] = characters[i];
characters[i] = temporary;
}
}
static void Main()
{
var results = new List<string>();
Generate("ABC".ToCharArray(), 0, results);
Console.WriteLine(string.Join(" ", results));
}
}Knowledge check
Questions students often ask
What is the main idea behind generate all string permutations?
Fix one position at a time by swapping each available character into it, recurse for the remaining positions, then undo the swap.
What is the time and space complexity of this solution?
Time O(n x n!), call-stack space O(n), excluding the output.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.