String Permutations

Permutations of a String

Generate all permutations of a given string using backtracking.

Backtracking Decision Tree

For input "abc", the algorithm explores all possible arrangements:

Algorithm Flow

How Backtracking Works

Step	Action	temp	Explanation
1	Add 'a'	"a"	Choose first character
2	Add 'b'	"ab"	Choose second character
3	Add 'c'	"abc"	Choose third → Complete!
4	Backtrack	"ab"	Remove 'c'
5	Backtrack	"a"	Remove 'b'
6	Add 'c'	"ac"	Try different choice
7	Add 'b'	"acb"	Complete!
...	...	...	Continue pattern

Complexity

• Time: $O(N \times N!)$ - N! permutations, each takes O(N) to build
• Space: $O(N)$ - recursion depth + temp string

Solution

public List<string> Permutations(string str)
{
    List<string> result = new List<string>();
    BacktrackPermutations(result, "", str);
    return result;
}

private void BacktrackPermutations(List<string> result, string temp, string str)
{
    if (temp.Length == str.Length)
    {
        result.Add(temp.ToString());
        return;
    }
    else
    {
        for (int i = 0; i < str.Length; i++)
        {
            if (temp.IndexOf(str[i]) >= 0) continue;  // Skip if already used
            temp = temp + str[i];                      // Choose
            BacktrackPermutations(result, temp, str);  // Explore
            temp = temp.Remove(temp.Length - 1);       // Un-choose (backtrack)
        }
    }
}

Key Insights

Interview Tips

• Backtracking pattern: Choose → Explore → Un-choose
• Duplicate handling: IndexOf check prevents reusing characters
• For unique permutations with duplicates: Sort first, then skip str[i] == str[i-1]

Limitation

This solution assumes all characters are unique. For strings with duplicate characters (e.g., "aab"), use a frequency map or sorting-based approach.