# 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**.

#### Input:

An array // [‘A’, ‘B’, ‘C’]

#### Output:

[‘A’, ‘B’, ‘C’] [‘A’, ‘C’, ‘B’], [‘B’, ‘A’, ‘C’], [‘B’, ‘C’, ‘A’], [‘C’, ‘A’, ‘B’], [‘C’, ‘B’, ‘A’]

OR

ABC, ACB, BAC, BCA, CAB, CBA

#### Logic :

Backtracking algorithm

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

In this example, we use arrays as an input as strings in javascript are immutable.

#### Solution :

Please write comments if you can make the above solution more clean, optimize or testable.