JavaScript Algorithm: Generate All Permutations with Backtracking (Full Guide)

Generate Permutations in JavaScript

📌 What is This Algorithm?

The Generate Permutations algorithm finds all possible orderings of elements in a given array. Unlike combinations, the order matters.

💡 Example

Given an array "[1, 2, 3]", all possible permutations are:

  [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
  

🚀 How Does It Work?

This algorithm uses **recursion** and **backtracking** to explore all possible orderings of elements.

• Start with an input array.
• Swap elements at different positions.
• Recursively generate all arrangements.
• When a full permutation is reached, store it.

🛠️ Code Implementation

const swap = (arr, i, j) => {
  const newArray = [...arr];
  [newArray[i], newArray[j]] = [newArray[j], newArray[i]]; // Swapping elements ES6 way
  return newArray;
};

const permutations = (arr) => {
  const P = [];
  const permute = (arr, low, high) => {
    if (low === high) {
      P.push([...arr]);
      return P;
    }
    for (let i = low; i <= high; i++) {
      arr = swap(arr, low, i);
      permute(arr, low + 1, high);
    }
    return P;
  };
  return permute(arr, 0, arr.length - 1);
};

export { permutations };
  

📌 Example Usage

Let’s generate all permutations of "[1, 2, 3]":

import { permutations } from './your-file.js';

console.log(permutations([1, 2, 3]));

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

⏳ Time Complexity

The number of permutations is calculated as: "n! (factorial of n)".

The complexity is "O(n!)", which grows exponentially.

📌 Where is This Used?

• Generating unique arrangements of elements
• Solving puzzles like the Traveling Salesman Problem
• Finding possible password combinations
• Backtracking-based solutions in coding interviews