// 第 12 周 – 用递归生成全排列（回溯）
// 运行：java Permutations.java
import java.util.ArrayList;
import java.util.List;

public class Permutations {

    // 在前缀之后，依次尝试每一个尚未使用的元素，
    // 然后递归地排列其余部分；之后再“退回一步”。
    static void permute(List<Character> prefix, boolean[] used, char[] items, List<String> out) {
        if (prefix.size() == items.length) {          // 基本情况：一个完整的排列
            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);         // 回溯
            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)");
    }
}