Generate all permutations of a given array using backtracking
A permutation is a rearrangement of the elements in a list. A string/array of length n has n! permutation.
An array // ['A', 'B', 'C']
['A', 'B', 'C'] ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B'], ['C', 'B', 'A']
ABC, ACB, BAC, BCA, CAB, CBA
- Iterate over the string one character at a time.
- Fix a character at the first position and the use swap to put every character at the first position
- Make recursive call to rest of the characters.
- Use swap to revert the string back to its original form for next iteration.
Time Complexity: O (n*n!)
Please write comments if you can make the above solution more clean, optimize or testable.