All Permutation String

Input abc -> abc, acb, bac, bca, cba, cab

Solution: "swap swap"

Base Case: if (index == input.length) return

Recursive Rule:

1. branch N - Index times

2. swap index and i

3. call self on next index

4. swap index and i, undo swap

Implementation:

public void permutation(Char[] input, int index){ 
    if (index == input.length){
        System.out.println(input);
        return;
    }
    
    for (int i = index; i < input.length; i++){
        swap(input, i , index);
        permutation(input, index + 1); //check next char
        swap(input, i , index); //undo swap
    }
}

Time Comp: O(N!) or O(N! * N) if adding String to result[]

Space Comp: O(N levels)