Javascript Algorithm:Permutations (LeetCode)

Problem Statement:

Given an array nums of distinct integers, return all the possible

permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]

Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]

Output: [[1]]

Constraints:

1 <= nums.length <= 6

-10 <= nums[i] <= 10

All the integers of nums are unique.

Using Backtracking:

Solution 1:

let set = ["A", "B", "C"];

let permute = function (array) {

let result = [];

function backtrack(index) {

if (index == array.length) {

result.push([...array]);

}

else

{

for (let i = index; i < array.length; i++) {

//swaps

[array[i], array[index]] = [array[index], array[i]];

backtrack(index + 1);

//swaps

[array[index], array[i]] = [array[i], array[index]];

}

}

}

backtrack(0);

return result;

};

let result = permute(set);

console.log(result);

Output:

[

[ 'A', 'B', 'C' ],

[ 'A', 'C', 'B' ],

[ 'B', 'A', 'C' ],

[ 'B', 'C', 'A' ],

[ 'C', 'A', 'B' ],

[ 'C', 'B', 'A' ]

]

Solution 2:

function permute(nums) {

let result = [];

if (nums.length <= 1) {

return [nums];

}

for (let i = 0; i < nums.length; i++) {

let firstElement = nums[i];//first element

//remaining element array

let remaining = nums.filter((elem) => {

return elem != firstElement;

});

let perms = permute(remaining);

for (let perm of perms) {

perm.push(firstElement);

}

result.push(...perms);

}

return result;

}

let set = ["A", "B","C"];

let result = permute(set);

console.log(result);

Output:

[

[ 'A', 'B', 'C' ],

[ 'A', 'C', 'B' ],

[ 'B', 'A', 'C' ],

[ 'B', 'C', 'A' ],

[ 'C', 'A', 'B' ],

[ 'C', 'B', 'A' ]

]

Without Backtracking:

Solution 3:

let getPermutaions = function (array, r) {

let penultiMateSizePermutation;

let oneSizeSizePermutation;

let result = [];

switch (r) {

case 0:

return [];

case 1:

let oneLengthSubsets = array.reduce((acc, elm) => {

acc.push([elm]);

return acc;

}, []);

return oneLengthSubsets;

default:

penultiMateSizePermutation = getPermutaions(array, r - 1);

oneSizeSizePermutation = getPermutaions(array, 1);

for (let outerElem of penultiMateSizePermutation) {

for (let innerElem of oneSizeSizePermutation) {

if (!outerElem.includes(innerElem[0])) {

result.push([...outerElem, innerElem[0]]);

}

}

}

return result;

}

};

let permute = function (nums) {

return getPermutaions(nums,nums.length)

};

let set = ["A", "B", "C"];

let result = permute(set);

console.log(result);

Output:

[

[ 'A', 'B', 'C' ],

[ 'A', 'C', 'B' ],

[ 'B', 'A', 'C' ],

[ 'B', 'C', 'A' ],

[ 'C', 'A', 'B' ],

[ 'C', 'B', 'A' ]

]

Explanation:

Here if we replaced following code

let permute = function (nums) {

return getPermutaions(nums,nums.length)

};

with

let permute = function (nums) {

return getPermutaions(nums,2)

};

Output:

[

[ 'A', 'B' ],

[ 'A', 'C' ],

[ 'B', 'A' ],

[ 'B', 'C' ],

[ 'C', 'A' ],

[ 'C', 'B' ]

]

it gives all 2 length permutations of our set ["A", "B", "C"].