> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dfs-permutations/all-permutation.md).

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