Generate All Permutations of Array in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a permutation of an array?

A permutation is a way to arrange all elements of the array in every possible order without missing any element or repeating any position.

beginner

What is the base case in a recursive function to generate permutations?

The base case is when the starting index reaches the length of the array, meaning one complete permutation is formed and can be recorded or printed.

intermediate

Why do we swap elements during permutation generation?

Swapping elements helps to fix one element at the current position and then recursively generate permutations for the rest of the array, ensuring all orders are explored.

beginner

How many permutations does an array of length n have?

An array of length n has n! (n factorial) permutations, which means n × (n-1) × (n-2) × ... × 1 possible arrangements.

intermediate

What is the time complexity of generating all permutations of an array?

The time complexity is O(n × n!) because there are n! permutations and each permutation takes O(n) time to process or print.

What does the swap operation do in permutation generation?

A Sorts the array elements

B Deletes an element from the array

C Fixes an element at a position to explore permutations

D Duplicates elements in the array

Swapping fixes one element at the current position so the function can generate permutations of the remaining elements.

When do we stop the recursion in generating permutations?

A When the array is empty

B When the start index equals the array length

C After one swap operation

D When the array is sorted

Recursion stops when the start index reaches the length of the array, meaning a full permutation is formed.

How many permutations does an array with 3 elements have?

A 6

B 12

C 9

D 3

3 elements have 3! = 3 × 2 × 1 = 6 permutations.

What is the main idea behind generating all permutations?

A Fix one element and permute the rest recursively

B Sort the array repeatedly

C Remove duplicates from the array

D Reverse the array elements

The main idea is to fix one element at a time and recursively generate permutations of the remaining elements.

What is the output format after generating permutations of [1, 2]?

A [1, 2] only

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

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

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

The permutations of [1, 2] are [1, 2] and [2, 1].

Explain step-by-step how to generate all permutations of an array using recursion and swapping.

Think about fixing one element at a time and exploring all orders for the rest.

Describe the time complexity of generating all permutations and why it is that way.

Consider how many permutations exist and how much work each takes.

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