# All Permutation String

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

**Solution:** "swap swap"

**Base Case:** if (index == input.length) return&#x20;

**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)
