Generate All Permutations of Array in DSA Go - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with full array

↓

Choose element at index i

↓

Swap element i with element j

↓

Recurse on sub-array i+1 to end

↓

If at last index, record permutation

↓

Backtrack: swap back elements i and j

↩Back to choose next j

We pick each element in turn, swap it to the current position, recurse on the rest, then swap back to restore order.

Execution Sample

DSA Go

func permute(arr []int, start int, res *[][]int) {
  if start == len(arr) {
    *res = append(*res, append([]int{}, arr...))
    return
  }
  for i := start; i < len(arr); i++ {
    arr[start], arr[i] = arr[i], arr[start]
    permute(arr, start+1, res)
    arr[start], arr[i] = arr[i], arr[start]
  }
}

This Go function generates all permutations by swapping elements starting from 'start' index and recursing.

Execution Table

Step	Operation	Current Index (start)	Swapped Index (i)	Permutation Recorded	Array State
1	Start recursion	0	-	No	[1 2 3]
2	Swap arr[0] and arr[0]	0	0	No	[1 2 3]
3	Recurse with start=1	1	-	No	[1 2 3]
4	Swap arr[1] and arr[1]	1	1	No	[1 2 3]
5	Recurse with start=2	2	-	No	[1 2 3]
6	Swap arr[2] and arr[2]	2	2	No	[1 2 3]
7	Record permutation	-	-	Yes	[1 2 3]
8	Backtrack swap arr[2] and arr[2]	2	2	No	[1 2 3]
9	Backtrack swap arr[1] and arr[1]	1	1	No	[1 2 3]
10	Swap arr[1] and arr[2]	1	2	No	[1 3 2]
11	Recurse with start=2	2	-	No	[1 3 2]
12	Swap arr[2] and arr[2]	2	2	No	[1 3 2]
13	Record permutation	-	-	Yes	[1 3 2]
14	Backtrack swap arr[2] and arr[2]	2	2	No	[1 3 2]
15	Backtrack swap arr[1] and arr[2]	1	2	No	[1 2 3]
16	Backtrack swap arr[0] and arr[0]	0	0	No	[1 2 3]
17	Swap arr[0] and arr[1]	0	1	No	[2 1 3]
18	Recurse with start=1	1	-	No	[2 1 3]
19	Swap arr[1] and arr[1]	1	1	No	[2 1 3]
20	Recurse with start=2	2	-	No	[2 1 3]
21	Swap arr[2] and arr[2]	2	2	No	[2 1 3]
22	Record permutation	-	-	Yes	[2 1 3]
23	Backtrack swap arr[2] and arr[2]	2	2	No	[2 1 3]
24	Backtrack swap arr[1] and arr[1]	1	1	No	[2 1 3]
25	Swap arr[1] and arr[2]	1	2	No	[2 3 1]
26	Recurse with start=2	2	-	No	[2 3 1]
27	Swap arr[2] and arr[2]	2	2	No	[2 3 1]
28	Record permutation	-	-	Yes	[2 3 1]
29	Backtrack swap arr[2] and arr[2]	2	2	No	[2 3 1]
30	Backtrack swap arr[1] and arr[2]	1	2	No	[2 1 3]
31	Backtrack swap arr[0] and arr[1]	0	1	No	[1 2 3]
32	Swap arr[0] and arr[2]	0	2	No	[3 2 1]
33	Recurse with start=1	1	-	No	[3 2 1]
34	Swap arr[1] and arr[1]	1	1	No	[3 2 1]
35	Recurse with start=2	2	-	No	[3 2 1]
36	Swap arr[2] and arr[2]	2	2	No	[3 2 1]
37	Record permutation	-	-	Yes	[3 2 1]
38	Backtrack swap arr[2] and arr[2]	2	2	No	[3 2 1]
39	Backtrack swap arr[1] and arr[1]	1	1	No	[3 2 1]
40	Swap arr[1] and arr[2]	1	2	No	[3 1 2]
41	Recurse with start=2	2	-	No	[3 1 2]
42	Swap arr[2] and arr[2]	2	2	No	[3 1 2]
43	Record permutation	-	-	Yes	[3 1 2]
44	Backtrack swap arr[2] and arr[2]	2	2	No	[3 1 2]
45	Backtrack swap arr[1] and arr[2]	1	2	No	[3 2 1]
46	Backtrack swap arr[0] and arr[2]	0	2	No	[1 2 3]
47	End recursion	-	-	No	[1 2 3]

💡 All permutations generated when start index reaches array length

Variable Tracker

Variable	Start	After Step 2	After Step 10	After Step 17	After Step 32	Final
arr	[1 2 3]	[1 2 3]	[1 3 2]	[2 1 3]	[3 2 1]	[1 2 3]
start	0	0	0	0	0	End
i	-	0	2	1	2	-
res (permutations count)	0	0	1	2	4	6

Key Moments - 3 Insights

Why do we swap elements back after recursion?

Swapping back restores the array to its original order before the next iteration, as shown in steps 8, 14, 15, 30, 39, 45, and 46 in the execution_table.

When do we record a permutation?

We record a permutation when the start index reaches the array length, meaning all positions are fixed. This happens at steps 7, 13, 22, 28, 37, and 43.

Why do we swap arr[start] with arr[i] inside the loop?

Swapping arr[start] with arr[i] places each possible element at the current position to explore all permutations, as seen in steps 2, 10, 17, and 32.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state at step 10?

A [2 1 3]

B [1 2 3]

C [1 3 2]

D [3 2 1]

💡 Hint

Check the 'Array State' column for step 10 in execution_table.

At which step is the first permutation recorded?

A Step 6

B Step 7

C Step 13

D Step 22

💡 Hint

Look for 'Record permutation' in the 'Operation' column and 'Yes' in 'Permutation Recorded'.

If we skip swapping back after recursion, what happens to the array state at step 15?

A [1 3 2]

B [1 2 3]

C [2 1 3]

D [3 2 1]

💡 Hint

Without swap back, the array remains changed from previous swap, check step 15 array state.

Concept Snapshot

Generate All Permutations of Array:
- Use recursion with a 'start' index.
- Swap current index with each index from start to end.
- Recurse with start+1.
- When start == len(arr), record permutation.
- Swap back to restore order (backtracking).

Full Transcript

This concept shows how to generate all permutations of an array using recursion and swapping. We start from index 0 and swap it with every index including itself. Then we recurse to fix the next index. When the start index reaches the array length, we record the current arrangement as a permutation. After each recursive call, we swap back the elements to restore the original order before trying the next swap. This ensures all permutations are explored without permanent changes to the array. The execution table traces each swap, recursion, and backtrack step with the array state, showing exactly how the array changes over time.

Practice

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

easy

A. Finding the largest element in the array

B. Sorting the array in ascending order

C. Listing all possible orders of the array elements

D. Removing duplicate elements from the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Compare options

   Only Listing all possible orders of the array elements describes listing all possible orders of elements.

3. Final Answer:

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

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 Go code snippet correctly starts a recursive function to generate permutations of an integer slice arr?

easy

A. func permute(arr int[], start int) {}

B. func permute(arr []int, start int) {}

C. func permute(arr []int, start string) {}

D. func permute(arr []int) {}

Solution

1. Step 1: Check Go function syntax

   Go uses []int for slices and int for integers; parameters must match expected types.

2. Step 2: Validate parameters for permutation

   We need the array slice and an integer index to track recursion start.

3. Final Answer:

   func permute(arr []int, start int) {} -> Option B

4. Quick Check:

   Correct Go slice and int params [OK]

Hint: Use []int for slices and int for indices [OK]

Common Mistakes:

• Using incorrect slice syntax like int[]
• Using wrong parameter types like string for index
• Omitting necessary parameters for recursion

3. What will be the output of this Go code snippet that generates permutations of []int{1, 2} and prints them?

func permute(arr []int, start int) {
  if start == len(arr) {
    fmt.Println(arr)
    return
  }
  for i := start; i < len(arr); i++ {
    arr[start], arr[i] = arr[i], arr[start]
    permute(arr, start+1)
    arr[start], arr[i] = arr[i], arr[start]
  }
}

func main() {
  permute([]int{1, 2}, 0)
}

medium

A. Compilation error

B. [2 1]
[1 2]

C. [1 2]

D. [1 2]
[2 1]

Solution

1. Step 1: Trace recursion for arr = [1, 2]

   Start=0: swap arr[0] with arr[0] -> [1,2], recurse start=1; then swap arr[0] with arr[1] -> [2,1], recurse start=1.

2. Step 2: Print when start == len(arr)

   At start=2, print current arr. So prints [1 2] then [2 1].

3. Final Answer:

   [1 2] [2 1] -> Option D

4. Quick Check:

   All permutations printed in order [OK]

Hint: Swap and backtrack to print all permutations [OK]

Common Mistakes:

• Not swapping back after recursion
• Printing before full permutation formed
• Confusing order of printed permutations

4. Identify the bug in this Go function intended to generate all permutations of arr:

func permute(arr []int, start int) {
  if start == len(arr) {
    fmt.Println(arr)
    return
  }
  for i := 0; i < len(arr); i++ {
    arr[start], arr[i] = arr[i], arr[start]
    permute(arr, start+1)
    arr[start], arr[i] = arr[i], arr[start]
  }
}

medium

A. Loop should start from 'start' instead of 0

B. Missing base case for recursion

C. Swapping elements is incorrect

D. Function should return a slice, not print

Solution

1. Step 1: Analyze loop range

   The loop runs from i=0 to len(arr), but it should start from 'start' to avoid duplicate swaps.

2. Step 2: Understand impact of loop start

   Starting from 0 causes repeated permutations and incorrect swapping order.

3. Final Answer:

   Loop should start from 'start' instead of 0 -> Option A

4. Quick Check:

   Loop start index = start [OK]

Hint: Loop from start index to avoid duplicates [OK]

Common Mistakes:

• Looping from zero causing repeated permutations
• Not swapping back after recursion
• Ignoring base case correctness

5. Given an array []int{1, 2, 3}, how many unique permutations will be generated by a correct permutation function, and why?

hard

A. 6, because 3! (3 factorial) = 6 permutations

B. 3, because there are 3 elements

C. 9, because 3 * 3 = 9 combinations

D. 1, because the array is fixed

Solution

1. Step 1: Calculate permutations count for 3 elements

   Number of permutations = factorial of number of elements = 3! = 3*2*1 = 6.

2. Step 2: Understand why other options are incorrect

   3 is just count of elements, 9 is product not permutations, 1 is incorrect as array can reorder.

3. Final Answer:

   6, because 3! (3 factorial) = 6 permutations -> Option A

4. Quick Check:

   Permutations of 3 elements = 6 [OK]

Hint: Permutations count = factorial of array length [OK]

Common Mistakes:

• Confusing permutations count with array length
• Using multiplication instead of factorial
• Thinking only one arrangement exists