Generate All Permutations of Array in DSA Javascript - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with empty permutation

↓

Pick each element not used

↓

Add element to current permutation

↓

If permutation complete?

No→Backtrack: remove last element

|Yes↓

Save permutation

↓

Repeat for all elements

Build permutations by choosing unused elements one by one, adding them to current list, saving when full, then backtracking to try others.

Execution Sample

DSA Javascript

function permute(arr) {
  const result = [];
  function backtrack(path, used) {
    if (path.length === arr.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(arr[i]);
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }
  backtrack([], Array(arr.length).fill(false));
  return result;
}

This code generates all permutations of an array by building paths recursively and backtracking.

Execution Table

Step	Operation	Current Path	Used Array	Action	Permutations Collected
1	Start backtrack	[]	[false, false, false]	Try elements 0,1,2	[]
2	Choose element 0	[1]	[true, false, false]	Recurse deeper	[]
3	Choose element 1	[1, 2]	[true, true, false]	Recurse deeper	[]
4	Choose element 2	[1, 2, 3]	[true, true, true]	Path complete, save	[[1,2,3]]
5	Backtrack	[1, 2]	[true, true, false]	Remove last element	[[1,2,3]]
6	Choose element 2	[1, 3]	[true, false, true]	Recurse deeper	[[1,2,3]]
7	Choose element 1	[1, 3, 2]	[true, true, true]	Path complete, save	[[1,2,3],[1,3,2]]
8	Backtrack	[1, 3]	[true, false, true]	Remove last element	[[1,2,3],[1,3,2]]
9	Backtrack	[1]	[true, false, false]	Remove last element	[[1,2,3],[1,3,2]]
10	Choose element 1	[2]	[false, true, false]	Recurse deeper	[[1,2,3],[1,3,2]]
11	Choose element 0	[2, 1]	[true, true, false]	Recurse deeper	[[1,2,3],[1,3,2]]
12	Choose element 2	[2, 1, 3]	[true, true, true]	Path complete, save	[[1,2,3],[1,3,2],[2,1,3]]
13	Backtrack	[2, 1]	[true, true, false]	Remove last element	[[1,2,3],[1,3,2],[2,1,3]]
14	Choose element 2	[2, 3]	[false, true, true]	Recurse deeper	[[1,2,3],[1,3,2],[2,1,3]]
15	Choose element 0	[2, 3, 1]	[true, true, true]	Path complete, save	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
16	Backtrack	[2, 3]	[false, true, true]	Remove last element	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
17	Backtrack	[2]	[false, true, false]	Remove last element	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
18	Choose element 2	[3]	[false, false, true]	Recurse deeper	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
19	Choose element 0	[3, 1]	[true, false, true]	Recurse deeper	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
20	Choose element 1	[3, 1, 2]	[true, true, true]	Path complete, save	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
21	Backtrack	[3, 1]	[true, false, true]	Remove last element	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
22	Choose element 1	[3, 2]	[false, true, true]	Recurse deeper	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
23	Choose element 0	[3, 2, 1]	[true, true, true]	Path complete, save	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
24	Backtrack	[3, 2]	[false, true, true]	Remove last element	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
25	Backtrack	[3]	[false, false, true]	Remove last element	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
26	Backtrack	[]	[false, false, false]	All permutations generated	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

💡 All elements tried at all positions; all permutations collected.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 12	After Step 15	After Step 23	Final
path	[]	[1]	[1,2,3]	[1,3,2]	[2,1]	[2,3,1]	[3,2,1]	[]
used	[false,false,false]	[true,false,false]	[true,true,true]	[true,false,true]	[true,true,false]	[true,true,true]	[true,true,true]	[false,false,false]
result	[]	[]	[[1,2,3]]	[[1,2,3],[1,3,2]]	[[1,2,3],[1,3,2],[2,1,3]]	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Key Moments - 3 Insights

Why do we need to mark elements as 'used'?

Marking elements as 'used' prevents choosing the same element multiple times in one permutation, as shown in execution_table rows 2-4 where used array changes to true for chosen elements.

Why do we remove the last element after recursion?

Removing the last element (backtracking) allows trying other elements in that position, as seen in execution_table rows 5 and 8 where path pops last element to explore new branches.

When do we know a permutation is complete?

When the current path length equals the original array length, we save the permutation, as shown in execution_table rows 4, 7, 12, 15, 20, 23 where path length matches array length.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the current path?

A [1, 2, 3]

B [1, 3, 2]

C [2, 1, 3]

D [3, 2, 1]

💡 Hint

Check the 'Current Path' column at step 4 in the execution_table.

At which step does the algorithm first backtrack by removing the last element?

A Step 3

B Step 5

C Step 7

D Step 10

💡 Hint

Look for 'Backtrack' operation and 'Remove last element' action in execution_table.

If the input array had 4 elements instead of 3, how would the 'Used Array' length change in variable_tracker?

A It would stay length 3

B It would become length 2

C It would become length 4

D It would be empty

💡 Hint

Used array length matches input array length, see variable_tracker 'used' row.

Concept Snapshot

Generate All Permutations of Array:
- Use backtracking to build permutations.
- Track used elements to avoid repeats.
- Add element to path, recurse, then remove (backtrack).
- Save path when length equals array length.
- Explore all element orders systematically.

Full Transcript

This visualization shows how to generate all permutations of an array using backtracking. We start with an empty path and try each unused element in turn. When the path length matches the array length, we save the permutation. After exploring one choice, we backtrack by removing the last element and marking it unused to try other options. The execution table tracks each step, showing the current path, which elements are used, and the permutations collected so far. The variable tracker shows how path, used array, and result change over time. Key moments clarify why we mark elements used, why backtracking is needed, and when permutations are complete. The quiz tests understanding of these steps and data states.

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