// 12. hét – Permutációk előállítása rekurzióval (visszalépéses keresés)
// Futtatás: java Permutations.java
import java.util.ArrayList;
import java.util.List;

public class Permutations {

    // A prefix után sorra minden még fel nem használt elemet kipróbálunk,
    // majd a maradékot rekurzívan permutáljuk; utána "visszalépünk".
    static void permute(List<Character> prefix, boolean[] used, char[] items, List<String> out) {
        if (prefix.size() == items.length) {          // alapeset: teljes permutáció
            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);         // visszalépés
            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("ABC permutációi: " + out + " (3! = " + out.size() + ")");
        out.clear();
        permute(new ArrayList<>(), new boolean[5], "ABCDE".toCharArray(), out);
        System.out.println("ABCDE permutációinak száma: " + out.size() + " (5! = 120)");
    }
}