Generate Permutations in Java
Problem
A permutation is one specific ordering of a set of characters — generating all of them means trying every character in every position, one fixed choice at a time.
Given a short string, print every possible arrangement of its characters.
Java Program
public class GeneratePermutations {
static void permute(char[] chars, int start) {
if (start == chars.length - 1) {
System.out.println(new String(chars));
return;
}
for (int i = start; i < chars.length; i++) {
swap(chars, start, i);
permute(chars, start + 1);
swap(chars, start, i); // backtrack: restore order before trying the next swap
}
}
static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
public static void main(String[] args) {
String s = "ABC";
permute(s.toCharArray(), 0);
}
}Output
Core Logic
Fixing one character into the current position, recursing to fill the rest, and then swapping back before trying the next candidate explores every ordering without ever building a separate copy of the string.
- 1
permute(chars, start)treats everything beforestartas already fixed in place. - 2The base case
start == chars.length - 1means every position is fixed, so the current arrangement is a complete permutation, printed directly. - 3The loop swaps each character from
startonward into thestartposition, recurses one position deeper, then swaps back — that swap-back is the backtrack step. - 4Swapping back restores the array to how it looked before this branch, so the next iteration of the loop tries its candidate against a clean, correctly-ordered array.
"ABC", fixing A first explores ABC and ACB; fixing B first explores BAC and BCA; fixing C first explores CBA and CAB — six permutations in total.Key Point: The swap-back after each recursive call is what makes this backtracking — without it, later iterations of the loop would keep operating on an array left in a jumbled state by the previous branch.
Why: There are n! distinct orderings to print, but the recursion only ever nests n calls deep, one per position being fixed.