C# Program to Find All Permutations of a String

You can find all permutations of a string in C# by using a recursive method that swaps characters and explores all possible orders, like Permute(char[] arr, int start, int end) which swaps characters and recursively generates permutations.

Examples

Input"abc"

Output["abc", "acb", "bac", "bca", "cab", "cba"]

Input"a"

Output["a"]

Input"ab"

Output["ab", "ba"]

How to Think About It

To find all permutations, think of fixing one character at a time and swapping it with every other character in the string. Then, recursively find permutations of the remaining characters. This way, you explore every possible order by swapping and backtracking.

Algorithm

1

Convert the input string to a character array.

2

Start from the first character and swap it with every character including itself.

3

Recursively call the function for the next position.

4

When the start index reaches the end, record the current permutation.

5

Backtrack by swapping characters back to restore the original array before the next swap.

Code

csharp

using System;
using System.Collections.Generic;

class Program {
    static void Permute(char[] arr, int start, int end, List<string> result) {
        if (start == end) {
            result.Add(new string(arr));
        } else {
            for (int i = start; i <= end; i++) {
                Swap(arr, start, i);
                Permute(arr, start + 1, end, result);
                Swap(arr, start, i); // backtrack
            }
        }
    }

    static void Swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void Main() {
        string input = "abc";
        List<string> permutations = new List<string>();
        Permute(input.ToCharArray(), 0, input.Length - 1, permutations);
        foreach (var p in permutations) {
            Console.WriteLine(p);
        }
    }
}

Output

abc
acb
bac
bca
cab
cba

Dry Run

Let's trace the input "abc" through the code to see how permutations are generated.

1

Initial call

Permute(['a','b','c'], 0, 2, result) with result = []

2

First level swaps

Swap positions 0 and 0: ['a','b','c'], call Permute(['a','b','c'], 1, 2, result)

3

Second level swaps

Swap positions 1 and 1: ['a','b','c'], call Permute(['a','b','c'], 2, 2, result) -> add "abc"

4

Backtrack and swap

Swap positions 1 and 2: ['a','c','b'], call Permute(['a','c','b'], 2, 2, result) -> add "acb"

5

Backtrack to first level

Swap back positions 1 and 2: ['a','b','c'], then swap positions 0 and 1: ['b','a','c'], call Permute(['b','a','c'], 1, 2, result)

6

Repeat second level swaps

Swap positions 1 and 1: ['b','a','c'], add "bac"; swap positions 1 and 2: ['b','c','a'], add "bca"

7

Backtrack to first level again

Swap back positions 1 and 2: ['b','a','c'], swap back positions 0 and 1: ['a','b','c'], swap positions 0 and 2: ['c','b','a'], call Permute(['c','b','a'], 1, 2, result)

8

Final second level swaps

Swap positions 1 and 1: ['c','b','a'], add "cba"; swap positions 1 and 2: ['c','a','b'], add "cab"

Permutation Generated
abc
acb
bac
bca
cab
cba

Why This Works

Step 1: Recursive swapping

The code swaps characters starting from the current index to the end, exploring all possible characters in that position.

Step 2: Base case records permutation

When the start index reaches the end, the current arrangement is a complete permutation and is added to the result list.

Step 3: Backtracking restores order

After exploring one swap, the code swaps back to restore the original order before trying the next swap, ensuring all permutations are found.

Alternative Approaches

Using Heap's Algorithm

csharp

using System;
using System.Collections.Generic;

class Program {
    static void HeapPermute(char[] arr, int size, List<string> result) {
        if (size == 1) {
            result.Add(new string(arr));
            return;
        }
        for (int i = 0; i < size; i++) {
            HeapPermute(arr, size - 1, result);
            if (size % 2 == 1) {
                Swap(arr, 0, size - 1);
            } else {
                Swap(arr, i, size - 1);
            }
        }
    }

    static void Swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void Main() {
        string input = "abc";
        List<string> permutations = new List<string>();
        HeapPermute(input.ToCharArray(), input.Length, permutations);
        foreach (var p in permutations) {
            Console.WriteLine(p);
        }
    }
}

Heap's algorithm generates permutations with fewer swaps on average, which can be more efficient for larger inputs.

Using LINQ and recursion

csharp

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static IEnumerable<string> GetPermutations(string str) {
        if (str.Length == 1) return new List<string> { str };
        return str.SelectMany((c, i) => GetPermutations(str.Remove(i,1))
            .Select(s => c + s));
    }

    static void Main() {
        foreach (var p in GetPermutations("abc")) {
            Console.WriteLine(p);
        }
    }
}

This approach uses LINQ for a concise and readable solution but may be less efficient due to string operations and allocations.

Complexity: O(n! * n) time, O(n) space

Time Complexity

Generating all permutations requires factorial time O(n!) because there are n! permutations. Each permutation takes O(n) time to copy or print.

Space Complexity

The recursion stack uses O(n) space for the call depth, and the character array is modified in place, so no extra large memory is needed.

Which Approach is Fastest?

The swapping backtracking method is generally faster and uses less memory than LINQ or other string-based methods. Heap's algorithm can reduce swaps but is similar in complexity.

Approach	Time	Space	Best For
Backtracking with swapping	O(n! * n)	O(n)	General use, efficient for moderate n
Heap's Algorithm	O(n! * n)	O(n)	Efficient swaps, good for large n
LINQ recursion	O(n! * n^2)	O(n^2)	Readable code, small inputs