// Week 12 – Generating permutations with recursion (backtracking)
// Run: java Permutations.java
import java.util.ArrayList;
import java.util.List;

public class Permutations {

    // After the prefix we try every element not used yet in turn,
    // then permute the rest recursively; afterwards we "step back".
    static void permute(List<Character> prefix, boolean[] used, char[] items, List<String> out) {
        if (prefix.size() == items.length) {          // base case: a complete permutation
            StringBuilder sb = new StringBuilder();
            for (char c : prefix) sb.append(c);
            out.add(sb.toString());
            return;
        }
        for (int i = 0; i < items.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            prefix.add(items[i]);
            permute(prefix, used, items, out);
            prefix.remove(prefix.size() - 1);         // backtracking
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        List<String> out = new ArrayList<>();
        permute(new ArrayList<>(), new boolean[3], "ABC".toCharArray(), out);
        System.out.println("permutations of ABC: " + out + " (3! = " + out.size() + ")");
        out.clear();
        permute(new ArrayList<>(), new boolean[5], "ABCDE".toCharArray(), out);
        System.out.println("number of permutations of ABCDE: " + out.size() + " (5! = 120)");
    }
}