Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

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.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *