Generate All Permutations of Array in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Permutations Function for [1, 2]

What is the output of the following TypeScript code that generates all permutations of the array [1, 2]?

DSA Typescript

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(start: number) {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }
  backtrack(0);
  return result;
}

console.log(permute([1, 2]));

A [[1,2],[2,1]]

B [[2,1],[1,2]]

C [[1,2]]

D [[2,1]]

💡 Hint

Think about all ways to arrange two numbers.

The function generates all permutations by swapping elements. For [1, 2], the permutations are [1, 2] and [2, 1].

❓ Predict Output

intermediate

Number of Permutations for Array [1, 2, 3]

What is the number of permutations generated by the following code for the array [1, 2, 3]?

DSA Typescript

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(start: number) {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }
  backtrack(0);
  return result;
}

const permutations = permute([1, 2, 3]);
console.log(permutations.length);

A 3

B 6

C 9

D 12

💡 Hint

Number of permutations of n distinct elements is n factorial.

For 3 elements, the number of permutations is 3! = 6.

🔧 Debug

advanced

Identify the Error in Permutation Code

What error will this TypeScript code produce when trying to generate permutations of [1, 2, 3]?

DSA Typescript

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(start: number) {
    if (start === nums.length) {
      result.push(nums);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }
  backtrack(0);
  return result;
}

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

A The output contains multiple references to the same array, causing all permutations to be identical.

B SyntaxError due to missing semicolon.

C TypeError because result.push is called with a number instead of an array.

D Runtime error due to infinite recursion.

💡 Hint

Check how arrays are added to the result.

The code pushes the original nums array reference multiple times without copying it, so all entries in result point to the same array, which ends up as the last permutation.

🧠 Conceptual

advanced

Understanding Backtracking in Permutations

In the backtracking approach to generate permutations, why do we swap elements back after the recursive call?

A To remove duplicate permutations from the result.

B To sort the array after each permutation is generated.

C To avoid infinite recursion by limiting the depth.

D To restore the original array state so other permutations can be generated correctly.

💡 Hint

Think about how the array changes during recursion.

Swapping back restores the array to its previous state so the next iterations can generate new permutations without interference.

🚀 Application

expert

Permutations with Duplicate Elements

Given the array [1, 1, 2], which option correctly outputs all unique permutations using backtracking?

DSA Typescript

function permuteUnique(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];
  const used = new Array(nums.length).fill(false);
  function backtrack(path: number[]) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }
  backtrack([]);
  return result;
}

console.log(permuteUnique([1, 1, 2]));

A [[1,1,2],[2,1,1]]

B [[1,1,2],[1,2,1],[2,1,1],[1,1,2]]

C [[1,1,2],[1,2,1],[2,1,1]]

D [[1,2,1],[2,1,1]]

💡 Hint

Duplicates are skipped by checking previous usage.

The code sorts the array and skips duplicates by checking if the previous identical element was used, ensuring unique permutations only.

Practice

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

easy

A. Listing all possible orders of the array elements

B. Sorting the array in ascending order

C. Removing duplicate elements from the array

D. Finding the largest element in the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array

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

3. Final Answer:

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

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
• Mixing permutations with finding max element

2. Which of the following TypeScript function signatures correctly represents a function that generates all permutations of an array of numbers?

easy

A. function permute(arr: number[][]): number[]

B. function permute(arr: number): number[]

C. function permute(arr: number[]): number[][]

D. function permute(arr: string[]): string

Solution

1. Step 1: Analyze input and output types

   The input is an array of numbers, so type is number[]. The output is all permutations, which is an array of arrays of numbers, so number[][].

2. Step 2: Match function signature

   function permute(arr: number[]): number[][] matches input number[] and output number[][] correctly.

3. Final Answer:

   function permute(arr: number[]): number[][] -> Option C

4. Quick Check:

   Input array, output array of arrays [OK]

Hint: Input array, output array of arrays for permutations [OK]

Common Mistakes:

• Using single number instead of array as input
• Returning a single array instead of array of arrays
• Mixing string and number types incorrectly

3. What is the output of the following TypeScript code?

function permute(arr: number[]): number[][] {
  if (arr.length === 0) return [[]];
  const result: number[][] = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const perm of permute(rest)) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

console.log(permute([1, 2]));

medium

A. [[1, 2], [2, 1]]

B. [[1, 2]]

C. [[2, 1]]

D. []

Solution

1. Step 1: Understand base case and recursion

   Base case returns [[]] for empty array. For [1,2], it picks each element and permutes the rest.

2. Step 2: Trace recursive calls for [1,2]

   First i=0: arr[i]=1, rest=[2], permute([2]) returns [[2]], so push [1,2]. Then i=1: arr[i]=2, rest=[1], permute([1]) returns [[1]], so push [2,1].

3. Final Answer:

   [[1, 2], [2, 1]] -> Option A

4. Quick Check:

   Permutations of [1,2] = [[1,2],[2,1]] [OK]

Hint: Check base case and recursive build-up [OK]

Common Mistakes:

• Forgetting to include all permutations
• Returning only one permutation
• Confusing order of elements

4. Identify the error in this TypeScript function that attempts to generate all permutations of an array:

function permute(arr: number[]): number[][] {
  if (arr.length === 1) return [arr];
  const result: number[][] = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = arr.slice(1);
    for (const perm of permute(rest)) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

medium

A. The base case should return an empty array

B. The function should return a flat array, not nested arrays

C. The loop should start from 1 instead of 0

D. The slice should exclude the current element, not always the first

Solution

1. Step 1: Analyze the slice operation

   The code uses arr.slice(1) always, which removes only the first element, not the current element at index i.

2. Step 2: Correct slice to exclude current element

   To generate permutations correctly, slice should exclude arr[i], e.g., [...arr.slice(0, i), ...arr.slice(i + 1)].

3. Final Answer:

   The slice should exclude the current element, not always the first -> Option D

4. Quick Check:

   Exclude current element in slice [OK]

Hint: Slice must exclude current index element [OK]

Common Mistakes:

• Always slicing from index 1 ignoring i
• Wrong base case length check
• Returning wrong data structure

5. Given an array with possible duplicate elements, how can you modify the permutation generation function to avoid duplicate permutations?

function permuteUnique(arr: number[]): number[][] {
  // Your code here
}

hard

A. Use a Set to store all permutations after generation

B. Sort the array first and skip duplicates during recursion

C. Remove duplicates from the array before generating permutations

D. Generate permutations normally without any change

Solution

1. Step 1: Understand duplicate permutations problem

   Duplicates in input cause repeated permutations if not handled.

2. Step 2: Sort and skip duplicates during recursion

   Sorting helps group duplicates. During recursion, skip elements equal to previous to avoid repeated branches.

3. Step 3: Why other options fail

   Using Set after generation is costly. Removing duplicates loses valid permutations. No change causes duplicates.

4. Final Answer:

   Sort the array first and skip duplicates during recursion -> Option B

5. Quick Check:

   Sort + skip duplicates = unique permutations [OK]

Hint: Sort array and skip duplicates in recursion [OK]

Common Mistakes:

• Removing duplicates from input loses valid permutations
• Using Set after generation wastes time and memory
• Ignoring duplicates causes repeated permutations