Print all the permutations of the given string
Problem
Print every ordering of the string's characters. If characters repeat, print each distinct permutation only once.
Example 1
Input: "abc" Output: abc, acb, bac, bca, cab, cba
Example 2
Input: "aab" Output: aab, aba, baa
Also asked as: permutations · Print all permutations of a string
Test cases
Case 1
Input: [1,2,3] Expected (any order): [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Case 2
Input: ["a","b"] Expected (any order): [["a","b"],["b","a"]]
Case 3
Input: [1] Expected (any order): [[1]]
View solutionHide solution2 approaches
1. Backtracking with a used[] array
Time O(n! · n)Space O(n)
Pick an unused element for the current position, recurse, then release it.
function permutations(arr) { const res = [], path = [], used = Array(arr.length).fill(false); const bt = () => { if (path.length === arr.length) { res.push([...path]); return; } for (let i = 0; i < arr.length; i++) { if (used[i]) continue; used[i] = true; path.push(arr[i]); bt(); path.pop(); used[i] = false; } }; bt(); return res;}2. In-place swap
Time O(n! · n)Space O(n)
Fix each element into the first position by swapping, recurse on the rest, swap back.
function permutations(arr) { const res = []; const bt = (k) => { if (k === arr.length) { res.push([...arr]); return; } for (let i = k; i < arr.length; i++) { [arr[k], arr[i]] = [arr[i], arr[k]]; bt(k + 1); [arr[k], arr[i]] = [arr[i], arr[k]]; } }; bt(0); return res;}