Generate All Permutations of Array in DSA Javascript

Mental Model

We want to list every possible order of the items in the array by swapping elements step by step.

Analogy: Imagine you have 3 different colored balls and want to see all ways to line them up on a shelf. You try placing each ball first, then arrange the rest in all possible ways.

[1, 2, 3]
 ↑
start with first element fixed, then swap others to create new orders

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Generate all possible orders of the array elements

Step 1: fix element at index 0 (1), permute rest [2,3]

[1, 2, 3]

Why: Start with first element fixed to build permutations of the rest

Step 2: fix element at index 1 (2), permute rest [3]

[1, 2, 3]

Why: Fix second element to generate permutations of remaining elements

Step 3: only one element left, add [1, 2, 3] to results

[1, 2, 3]

Why: Base case reached, record this permutation

Step 4: backtrack, swap elements at index 1 and 2 to get [1, 3, 2]

[1, 3, 2]

Why: Swap to create new permutation starting with 1

Step 5: fix element at index 1 (3), permute rest [2]

[1, 3, 2]

Why: Fix second element again to generate permutations

Step 6: only one element left, add [1, 3, 2] to results

[1, 3, 2]

Why: Base case reached, record this permutation

Step 7: backtrack, swap elements at index 0 and 1 to get [2, 1, 3]

[2, 1, 3]

Why: Change first element to 2 and repeat process

Step 8: fix element at index 1 (1), permute rest [3]

[2, 1, 3]

Why: Fix second element to generate permutations

Step 9: only one element left, add [2, 1, 3] to results

[2, 1, 3]

Why: Base case reached, record this permutation

Step 10: backtrack, swap elements at index 1 and 2 to get [2, 3, 1]

[2, 3, 1]

Why: Swap to create new permutation starting with 2

Step 11: fix element at index 1 (3), permute rest [1]

[2, 3, 1]

Why: Fix second element again to generate permutations

Step 12: only one element left, add [2, 3, 1] to results

[2, 3, 1]

Why: Base case reached, record this permutation

Step 13: backtrack, swap elements at index 0 and 2 to get [3, 2, 1]

[3, 2, 1]

Why: Change first element to 3 and repeat process

Step 14: fix element at index 1 (2), permute rest [1]

[3, 2, 1]

Why: Fix second element to generate permutations

Step 15: only one element left, add [3, 2, 1] to results

[3, 2, 1]

Why: Base case reached, record this permutation

Step 16: backtrack, swap elements at index 1 and 2 to get [3, 1, 2]

[3, 1, 2]

Why: Swap to create new permutation starting with 3

Step 17: fix element at index 1 (1), permute rest [2]

[3, 1, 2]

Why: Fix second element again to generate permutations

Step 18: only one element left, add [3, 1, 2] to results

[3, 1, 2]

Why: Base case reached, record this permutation

Result:

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

Annotated Code

DSA Javascript

class Permutations {
  constructor() {
    this.results = []
  }

  generate(nums) {
    this.backtrack(nums, 0)
    return this.results
  }

  backtrack(nums, start) {
    if (start === nums.length - 1) {
      this.results.push([...nums])
      return
    }

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]] // swap
      this.backtrack(nums, start + 1) // recurse with next start
      [nums[start], nums[i]] = [nums[i], nums[start]] // backtrack swap
    }
  }
}

const perm = new Permutations()
const input = [1, 2, 3]
const output = perm.generate(input)
for (const arr of output) {
  console.log(arr)
}

[nums[start], nums[i]] = [nums[i], nums[start]] // swap

swap current start element with element at i to create new order

this.backtrack(nums, start + 1) // recurse with next start

move start forward to fix next element and generate permutations

[nums[start], nums[i]] = [nums[i], nums[start]] // backtrack swap

undo swap to restore original array before next iteration

if (start === nums.length - 1) { this.results.push([...nums]) return }

base case: all elements fixed, record current permutation

Output

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

Complexity Analysis

Time: O(n! * n) because there are n! permutations and copying each takes O(n)

Space: O(n! * n) to store all permutations and O(n) recursion stack for swaps

vs Alternative: This backtracking approach is efficient compared to generating permutations by repeated insertions which can be more complex and slower

Edge Cases

empty array []

returns empty list of permutations

DSA Javascript

if (start === nums.length - 1) { this.results.push([...nums]); return; }

array with one element [5]

returns [[5]] as the only permutation

DSA Javascript

if (start === nums.length - 1) { this.results.push([...nums]); return; }

array with duplicate elements [1,1]

returns all permutations including duplicates

DSA Javascript

no special guard; duplicates are handled naturally by swaps

When to Use This Pattern

When asked to list all possible orders or arrangements of items, use backtracking with swapping to generate permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursive call, causing wrong array state
Fix: Always swap back (backtrack) after recursion to restore original order

Mistake: Copying array reference instead of a new array when saving permutation
Fix: Use a copy like [...nums] to save current permutation snapshot

Summary

Generates all possible orders of an array by swapping elements recursively.

Use when you need every arrangement of items, like in puzzles or ordering problems.

The key is to fix one element at a time and swap others to explore all possibilities.

Practice

1. What does generating all permutations of an array mean?

easy

A. Finding the largest element in the array

B. Listing all possible orders of the array elements

C. Removing duplicate elements from the array

D. Sorting the array in ascending order

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array elements

   Generating permutations means listing every possible order of the array's elements.

3. Final Answer:

   Listing all possible orders of the array elements -> Option B

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all ways to arrange elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Believing permutations find max element

2. Which of the following is the correct syntax to start a recursive function for generating permutations in JavaScript?

easy

A. function permute(arr l r) { }

B. function permute(arr, l, r) => { }

C. permute function(arr, l, r) { }

D. function permute(arr, l, r) { }

Solution

1. Step 1: Recall JavaScript function syntax

   Functions are declared with the keyword 'function', parameters inside parentheses separated by commas.

2. Step 2: Check each option

   function permute(arr, l, r) { } uses correct syntax: function name, parameters with commas, and braces. function permute(arr, l, r) => { } uses arrow syntax incorrectly. permute function(arr, l, r) { } has wrong order. function permute(arr l r) { } misses commas.

3. Final Answer:

   function permute(arr, l, r) { } -> Option D

4. Quick Check:

   Correct function syntax = function permute(arr, l, r) { } [OK]

Hint: Use 'function name(params) { }' for recursive functions [OK]

Common Mistakes:

• Using arrow syntax without proper parameters
• Missing commas between parameters
• Incorrect function keyword placement

3. What is the output of the following code?

function permute(arr, l, r) {
  if (l === r) {
    console.log(arr.join(''));
  } else {
    for (let i = l; i <= r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]];
      permute(arr, l + 1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]];
    }
  }
}
permute(['A', 'B', 'C'], 0, 2);

medium

A. ABC, ACB, BAC, BCA, CAB, CBA

B. ABC, BAC, CAB

C. ABC only

D. SyntaxError

Solution

1. Step 1: Understand the recursive swapping

   The function swaps elements starting from index l to r, generating all permutations by recursive calls.

2. Step 2: Trace output for ['A','B','C']

   All 6 permutations of 3 elements are printed: ABC, ACB, BAC, BCA, CAB, CBA.

3. Final Answer:

   ABC, ACB, BAC, BCA, CAB, CBA -> Option A

4. Quick Check:

   All 3-element permutations = ABC, ACB, BAC, BCA, CAB, CBA [OK]

Hint: Swapping + recursion = all permutations [OK]

Common Mistakes:

• Missing swap back step causing wrong output
• Printing partial permutations only
• Confusing output order

4. Identify the error in this permutation function:

function permute(arr, l, r) {
  if (l === r) {
    console.log(arr.join(''));
  } else {
    for (let i = l; i < r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]];
      permute(arr, l + 1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]];
    }
  }
}
permute(['X', 'Y', 'Z'], 0, 2);

medium

A. The for loop should use i <= r instead of i < r

B. The swap syntax is incorrect

C. The base case condition should be l > r

D. The function should not use recursion

Solution

1. Step 1: Check loop boundary

   The loop runs from i = l to i < r, so it misses the last index r.

2. Step 2: Correct loop condition

   Changing to i <= r includes the last element, ensuring all permutations are generated.

3. Final Answer:

   The for loop should use i <= r instead of i < r -> Option A

4. Quick Check:

   Loop boundary must include r [OK]

Hint: Loop to r inclusive for full permutations [OK]

Common Mistakes:

• Using i < r misses last element
• Incorrect swap syntax causing errors
• Wrong base case stopping recursion early

5. Given an array with duplicate elements ['A', 'B', 'A'], how can you modify the permutation function to avoid printing duplicate permutations?

hard

A. Use a set to track and skip already generated permutations

B. Remove duplicates from the array before permutation

C. Sort the array and skip swapping identical elements at the same recursion level

D. No modification needed; duplicates are automatically avoided

Solution

1. Step 1: Understand duplicates in permutations

   Duplicates cause repeated permutations when identical elements are swapped.

2. Step 2: Skip swapping identical elements

   Sorting the array and checking if the element was already swapped at the current recursion level avoids duplicates.

3. Final Answer:

   Sort the array and skip swapping identical elements at the same recursion level -> Option C

4. Quick Check:

   Skip identical swaps after sorting to avoid duplicates [OK]

Hint: Sort + skip identical swaps to avoid duplicate permutations [OK]

Common Mistakes:

• Removing duplicates loses valid permutations
• Using set only after generating all permutations (inefficient)
• Assuming duplicates are avoided automatically