Print all the permutations of the given string

Medium

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]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}