Generate All Permutations of Array in DSA Typescript - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with empty permutation

↓

Choose element not in current permutation

↓

Add element to current permutation

↓

Is permutation complete?

No→Repeat choosing next element

Yes↓

Save current permutation

↓

Backtrack: Remove last element

↩Back to choosing element

Build permutations by adding unused elements one by one, save when full length reached, then backtrack to try other options.

Execution Sample

DSA Typescript

function permute(arr: number[]): number[][] {
  const result: number[][] = [];
  const backtrack = (temp: number[]) => {
    if (temp.length === arr.length) result.push([...temp]);
    else {
      for (const num of arr) {
        if (!temp.includes(num)) {
          temp.push(num);
          backtrack(temp);
          temp.pop();
        }
      }
    }
  };
  backtrack([]);
  return result;
}

Recursively build permutations by adding unused elements until full length, then save and backtrack.

Execution Table

Step	Operation	Current Permutation	Action	Visual State
1	Start backtrack with []	[]	Choose element 1	[1]
2	Add 1	[1]	Choose element 2	[1,2]
3	Add 2	[1,2]	Choose element 3	[1,2,3]
4	Add 3	[1,2,3]	Permutation complete, save	[1,2,3]
5	Backtrack	[1,2,3]	Remove 3	[1,2]
6	Backtrack	[1,2]	Remove 2	[1]
7	Choose element 3	[1]	Add 3	[1,3]
8	Add 3	[1,3]	Choose element 2	[1,3,2]
9	Add 2	[1,3,2]	Permutation complete, save	[1,3,2]
10	Backtrack	[1,3,2]	Remove 2	[1,3]
11	Backtrack	[1,3]	Remove 3	[1]
12	Backtrack	[1]	Remove 1	[]
13	Choose element 2	[]	Add 2	[2]
14	Add 2	[2]	Choose element 1	[2,1]
15	Add 1	[2,1]	Choose element 3	[2,1,3]
16	Add 3	[2,1,3]	Permutation complete, save	[2,1,3]
17	Backtrack	[2,1,3]	Remove 3	[2,1]
18	Backtrack	[2,1]	Remove 1	[2]
19	Choose element 3	[2]	Add 3	[2,3]
20	Add 3	[2,3]	Choose element 1	[2,3,1]
21	Add 1	[2,3,1]	Permutation complete, save	[2,3,1]
22	Backtrack	[2,3,1]	Remove 1	[2,3]
23	Backtrack	[2,3]	Remove 3	[2]
24	Backtrack	[2]	Remove 2	[]
25	Choose element 3	[]	Add 3	[3]
26	Add 3	[3]	Choose element 1	[3,1]
27	Add 1	[3,1]	Choose element 2	[3,1,2]
28	Add 2	[3,1,2]	Permutation complete, save	[3,1,2]
29	Backtrack	[3,1,2]	Remove 2	[3,1]
30	Backtrack	[3,1]	Remove 1	[3]
31	Choose element 2	[3]	Add 2	[3,2]
32	Add 2	[3,2]	Choose element 1	[3,2,1]
33	Add 1	[3,2,1]	Permutation complete, save	[3,2,1]
34	Backtrack	[3,2,1]	Remove 1	[3,2]
35	Backtrack	[3,2]	Remove 2	[3]
36	Backtrack	[3]	Remove 3	[]
37	All permutations generated	[]	End	All permutations saved

💡 All elements tried at all positions; recursion ends when all permutations saved.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 12	After Step 25	Final
current permutation (temp)	[]	[1]	[1,2,3]	[]	[3]	[]
result (saved permutations)	[]	[]	[[1,2,3]]	[[1,2,3],[1,3,2]]	[[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]]

Key Moments - 3 Insights

Why do we need to remove the last element after recursive call (backtrack)?

Removing the last element after recursion lets us try other elements in that position. See steps 4 and 5 where 3 is removed to try other options.

Why do we check if element is already in current permutation before adding?

To avoid duplicates in the permutation. The check prevents adding the same element twice, e.g., skips 1 and 2 when current is [1,2].

When do we know a permutation is complete?

When the current permutation length equals the original array length, like in step 4 where length 3 means complete permutation saved.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the current permutation?

A [1,2]

B [1,2,3]

C [1,3]

D []

💡 Hint

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

At which step does the algorithm backtrack after saving the permutation [2,3,1]?

A Step 23

B Step 21

C Step 22

D Step 24

💡 Hint

Look for 'Permutation complete, save' with [2,3,1] and then the next step showing 'Remove 1'.

If we remove the check for element already in permutation, what happens?

A Permutations will have duplicates of same element

B Algorithm will run faster

C No permutations will be generated

D Algorithm will crash

💡 Hint

Refer to key_moments about why we check if element is already in current permutation.

Concept Snapshot

Generate all permutations by:
- Recursively adding unused elements to current list
- When length equals input array, save permutation
- Backtrack by removing last element to try others
- Use check to avoid duplicates
- Result is all possible orderings

Full Transcript

This concept shows how to generate all permutations of an array by building them step-by-step. We start with an empty list and add elements one by one if they are not already used. When the current list length matches the original array length, we save that permutation. Then we remove the last element to try other possibilities, called backtracking. This process repeats until all permutations are found. The execution table traces each step, showing how the current permutation grows and shrinks, and when permutations are saved. Key moments explain why we remove elements after recursion and why we check for duplicates. The visual quiz tests understanding of these steps and effects of changes.