String Permutations: Backtracking Algorithm Implementation

Description

Given a string, generate all possible permutations of its characters. A permutation is an arrangement of objects where order matters. For example, given the string "abc", the algorithm should generate all six possible permutations: "abc", "acb", "bac", "bca", "cab", and "cba".

Examples:

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

Input: "12"
Output: ["12", "21"]

Input: "a"
Output: ["a"]

Approach

We'll solve this problem using backtracking. The basic idea is to:

Fix a character at the first position and recursively generate permutations for remaining positions
Swap characters to generate different permutations
Use backtracking to restore the original state after exploring each possibility

Algorithm Steps:

Convert the input string to a character array for easier manipulation
Create a recursive function that takes:
- The character array
- The current position being processed
- A list to store all permutations
Base case: If current position equals string length, add current permutation to result
For each position from current to end:
- Swap characters at current and i
- Recursively generate permutations for next position
- Backtrack by swapping back the characters

Implementation

def generate_permutations(s: str) -> List[str]:
    def backtrack(chars: List[str], start: int, result: List[str]):
        if start == len(chars):
            result.append(''.join(chars))
            return
            
        for i in range(start, len(chars)):
            # Swap characters
            chars[start], chars[i] = chars[i], chars[start]
            
            # Recursively generate permutations
            backtrack(chars, start + 1, result)
            
            # Backtrack by restoring original state
            chars[start], chars[i] = chars[i], chars[start]
    
    result = []
    backtrack(list(s), 0, result)
    return result

class Solution {
private:
    void backtrack(string& s, int start, vector& result) {
        if (start == s.length()) {
            result.push_back(s);
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            // Swap characters
            swap(s[start], s[i]);
            
            // Recursively generate permutations
            backtrack(s, start + 1, result);
            
            // Backtrack
            swap(s[start], s[i]);
        }
    }
    
public:
    vector generatePermutations(string s) {
        vector result;
        backtrack(s, 0, result);
        return result;
    }
};

public class Solution {
    private void Backtrack(char[] chars, int start, IList result) {
        if (start == chars.Length) {
            result.Add(new string(chars));
            return;
        }
        
        for (int i = start; i < chars.Length; i++) {
            // Swap characters
            (chars[start], chars[i]) = (chars[i], chars[start]);
            
            // Recursively generate permutations
            Backtrack(chars, start + 1, result);
            
            // Backtrack
            (chars[start], chars[i]) = (chars[i], chars[start]);
        }
    }
    
    public IList GeneratePermutations(string s) {
        var result = new List();
        Backtrack(s.ToCharArray(), 0, result);
        return result;
    }
}

Complexity Analysis

Operation	Time Complexity	Space Complexity
Generate All Permutations	O(n!)	O(n)

For a string of length n, there are n! possible permutations. The algorithm needs to generate all of them, so the time complexity is O(n!). The space complexity is O(n) where n is the length of the input string, accounting for the recursion stack and the character array used to store the current permutation.

Algorithm Visualization

Speed:

Enter a string and click Start

Algorithm Info

String Permutations