Generate All Permutations of Array in DSA Typescript

Mental Model

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

Analogy: Imagine you have 3 different colored balls and want to see all ways to arrange them in a row by swapping their positions.

Array: [1, 2, 3]
Indexes:  0  1  2
Start with first index and swap with each possible index to create new orders.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Generate all possible orders of the array elements

Step 1: Start with index 0, swap element at 0 with 0 (no change)

[1, 2, 3]

Why: Begin permutations by fixing first element and permuting the rest

Step 2: Move to index 1, swap element at 1 with 1 (no change)

[1, 2, 3]

Why: Fix second element and permute remaining elements

Step 3: Move to index 2, reached end, record permutation [1, 2, 3]

[1, 2, 3]

Why: Base case: one permutation completed

Step 4: Backtrack to index 1, swap element at 1 with 2

[1, 3, 2]

Why: Swap to create new permutation branch

Step 5: Move to index 2, reached end, record permutation [1, 3, 2]

[1, 3, 2]

Why: Base case: another permutation completed

Step 6: Backtrack to index 0, swap element at 0 with 1

[2, 1, 3]

Why: Change first element to generate new permutations

Step 7: At index 1, swap element at 1 with 1 (no change)

[2, 1, 3]

Why: Fix second element and permute rest

Step 8: At index 2, reached end, record permutation [2, 1, 3]

[2, 1, 3]

Why: Record new permutation

Result:

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

Annotated Code

DSA Typescript

class Permutations {
  private results: number[][] = [];

  public generate(nums: number[]): number[][] {
    this.backtrack(nums, 0);
    return this.results;
  }

  private backtrack(nums: number[], start: number): void {
    if (start === nums.length) {
      this.results.push([...nums]); // record current permutation
      return;
    }

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]]; // swap to fix element at start
      this.backtrack(nums, start + 1); // permute remaining elements
      [nums[start], nums[i]] = [nums[i], nums[start]]; // swap back to restore
    }
  }
}

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

if (start === nums.length) {

Base case: all positions fixed, record current permutation

this.results.push([...nums]);

Save a copy of current permutation

[nums[start], nums[i]] = [nums[i], nums[start]];

Swap to fix element at current start index

this.backtrack(nums, start + 1);

Recurse to fix next position

[nums[start], nums[i]] = [nums[i], nums[start]];

Swap back to restore original array for next iteration

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 permutation takes O(n)

Space: O(n) for recursion stack plus O(n! * n) for storing all permutations

vs Alternative: Compared to generating permutations by building new arrays each time, swapping in place reduces extra space but still requires factorial time due to permutation count

Edge Cases

empty array []

returns [[]] as the only permutation (empty permutation)

DSA Typescript

if (start === nums.length) {

array with one element [5]

returns [[5]] as the only permutation

DSA Typescript

if (start === nums.length) {

array with duplicate elements [1, 1]

returns all permutations including duplicates, e.g. [1,1] and [1,1]

DSA Typescript

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

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 incorrect array state
Fix: Always swap back after recursion to restore original order for next iteration

Mistake: Pushing reference to nums instead of a copy, causing all results to be the same
Fix: Push a copy of the array using spread operator or slice

Summary

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

Use when you need every arrangement of items, like permutations in puzzles or combinations.

The key is to fix one element at a time by swapping and backtracking to explore all options.