• 0

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

Permutations
Permutations

Logic :

Backtracking algorithm

  • Iterate over the string one character at a time.
    • Fix a character at the first posi­tion and the use swap to put every char­ac­ter at the first posi­tion
    • Make recur­sive call to rest of the characters.
    • Use swap to revert the string back to its orig­i­nal 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.