BackTrackingProblem 14 of 19
Print all permutations of a string
Problem Statement
Given a string, print all permutations of the string. A permutation is a rearrangement of the characters of the string.
Example:
Input: s = "ABC"
Output: ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
Input: s = "AB"
Output: ["AB", "BA"]
Explanation: All possible arrangements of the characters.
Approach 1: Brute Force (Swap-based Backtracking)
Intuition
Fix one character at each position and recursively generate permutations of the remaining characters. Use swapping to bring each character to the current position.
Algorithm
- Fix character at current index
- Swap current with each character from index to end
- Recurse for next index
- Backtrack by swapping back
java
import java.util.*;
class Solution {
public void permute(char[] s, int index, List<String> result) {
// Base case: reached end of string
if (index == s.length) {
result.add(new String(s));
return;
}
// Try each character at current position
for (int i = index; i < s.length; i++) {
// Swap
char temp = s[index];
s[index] = s[i];
s[i] = temp;
permute(s, index + 1, result);
// Backtrack
temp = s[index];
s[index] = s[i];
s[i] = temp;
}
}
public List<String> printAllPermutations(String s) {
List<String> result = new ArrayList<>();
permute(s.toCharArray(), 0, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(n × n!) - n! permutations, O(n) to copy each
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (Using Visited Array)
Intuition
Build permutations character by character. Use a visited array to track which characters have been used in the current permutation.
Algorithm
- Maintain a visited array
- For each position, try adding each unvisited character
- Mark as visited, recurse, then unmark
java
import java.util.*;
class Solution {
public void permute(String s, StringBuilder current, boolean[] visited,
List<String> result) {
// Base case: permutation complete
if (current.length() == s.length()) {
result.add(current.toString());
return;
}
for (int i = 0; i < s.length(); i++) {
if (!visited[i]) {
visited[i] = true;
current.append(s.charAt(i));
permute(s, current, visited, result);
current.deleteCharAt(current.length() - 1);
visited[i] = false;
}
}
}
public List<String> printAllPermutations(String s) {
List<String> result = new ArrayList<>();
boolean[] visited = new boolean[s.length()];
permute(s, new StringBuilder(), visited, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(n × n!) - n! permutations
- Space Complexity: O(n) - Visited array and recursion stack
Handling Duplicates (Unique Permutations)
Intuition
When string has duplicate characters, sort first and skip duplicates at the same level.
java
import java.util.*;
class Solution {
public void permute(char[] s, int index, List<String> result) {
if (index == s.length) {
result.add(new String(s));
return;
}
Set<Character> used = new HashSet<>();
for (int i = index; i < s.length; i++) {
if (used.contains(s[i])) continue;
used.add(s[i]);
char temp = s[index];
s[index] = s[i];
s[i] = temp;
permute(s, index + 1, result);
temp = s[index];
s[index] = s[i];
s[i] = temp;
}
}
public List<String> permuteUnique(String s) {
List<String> result = new ArrayList<>();
char[] arr = s.toCharArray();
Arrays.sort(arr);
permute(arr, 0, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(n × n!) worst case, better with duplicates
- Space Complexity: O(n) - Set and recursion stack
Using next_permutation (Iterative)
java
import java.util.*;
class Solution {
public boolean nextPermutation(char[] arr) {
int n = arr.length;
int i = n - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) i--;
if (i < 0) return false;
int j = n - 1;
while (arr[j] <= arr[i]) j--;
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Reverse from i+1 to end
int left = i + 1, right = n - 1;
while (left < right) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
return true;
}
public List<String> printAllPermutations(String s) {
List<String> result = new ArrayList<>();
char[] arr = s.toCharArray();
Arrays.sort(arr);
do {
result.add(new String(arr));
} while (nextPermutation(arr));
return result;
}
}Key Takeaways
- Swap Method: In-place permutation generation
- Visited Array: Alternative approach for building permutations
- Duplicate Handling: Use set at each level to skip duplicates
- LeetCode #46: Permutations (distinct elements)
- LeetCode #47: Permutations II (with duplicates)
- Factorial Growth: n! permutations for n distinct elements