VietMX Staff asked 3 years ago
A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation:
ABC // original string (3)ABC ACB BAC BCA CBA CAB // permutations 3! = 6To print all permutations of a string use backtracking implemented via recursion:
- Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call.
- The base case is when the input is an empty string the only permutation is the empty string.
- In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.
Complexity Analysis
For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!).The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!).
Implementation
// using backtrackinglet permute = (str, left = 0, right = str.length - 1) => { //If left index is equal to right 