Permutations of a String

Problem Statement

Given a string, generate all possible permutations of its characters. A permutation is a rearrangement of the string’s characters, and all must be unique if the string has duplicates. This medium-level problem dives into recursion and backtracking, exploring every possible order of characters—think of it as shuffling a deck of letters to see all combinations!

Example

Input: s = "abc"

Output: ["abc", "acb", "bac", "bca", "cab", "cba"] (all 3! = 6 permutations)

Input: s = "aab"

Output: ["aab", "aba", "baa"] (3 unique permutations due to duplicates)

Code

public class Solution {
    public List permute(String s) {
        List result = new ArrayList<>();
        char[] chars = s.toCharArray();
        backtrack(chars, 0, result);
        return result;
    }
    
    private void backtrack(char[] chars, int start, List result) {
        if (start == chars.length) {
            result.add(new String(chars));
            return;
        }
        Set used = new HashSet<>();
        for (int i = start; i < chars.length; i++) {
            if (!used.contains(chars[i])) {
                used.add(chars[i]);
                swap(chars, start, i);
                backtrack(chars, start + 1, result);
                swap(chars, start, i); // Backtrack
            }
        }
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
            

def permute(s):
    def backtrack(chars, start, result):
        if start == len(chars):
            result.append("".join(chars))
            return
        seen = set()
        for i in range(start, len(chars)):
            if chars[i] not in seen:
                seen.add(chars[i])
                chars[start], chars[i] = chars[i], chars[start]
                backtrack(chars, start + 1, result)
                chars[start], chars[i] = chars[i], chars[start]  # Backtrack
    
    result = []
    backtrack(list(s), 0, result)
    return result

# Example usage
print(permute("abc"))  # ["abc", "acb", "bac", "bca", "cab", "cba"]
print(permute("aab"))  # ["aab", "aba", "baa"]
            

function permute(s) {
    function backtrack(chars, start, result) {
        if (start === chars.length) {
            result.push(chars.join(""));
            return;
        }
        let seen = new Set();
        for (let i = start; i < chars.length; i++) {
            if (!seen.has(chars[i])) {
                seen.add(chars[i]);
                [chars[start], chars[i]] = [chars[i], chars[start]];
                backtrack(chars, start + 1, result);
                [chars[start], chars[i]] = [chars[i], chars[start]]; // Backtrack
            }
        }
    }
    
    let result = [];
    backtrack(s.split(""), 0, result);
    return result;
}

// Example usage
console.log(permute("abc")); // ["abc", "acb", "bac", "bca", "cab", "cba"]
console.log(permute("aab")); // ["aab", "aba", "baa"]
            

Explanation

• Base Case: When start reaches the string length, add the current permutation.
• Recursive Step: For each position, swap with every subsequent character and recurse.
• Backtracking: Undo swaps to restore the original state for the next iteration.
• Duplicates: Use a set to skip repeated characters at each level, ensuring unique permutations.
• Flow Example (s="ab"): Start with "ab" → swap to "ab" → recurse → "ab"; swap to "ba" → recurse → "ba".

Note