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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Permutations for a 3-Element Array

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

DSA Go

package main

import (
	"fmt"
)

func permute(nums []int, start int, result *[][]int) {
	if start == len(nums)-1 {
		// Make a copy of nums and append to result
		temp := make([]int, len(nums))
		copy(temp, nums)
		*result = append(*result, temp)
		return
	}
	for i := start; i < len(nums); i++ {
		nums[start], nums[i] = nums[i], nums[start]
		permute(nums, start+1, result)
		nums[start], nums[i] = nums[i], nums[start]
	}
}

func main() {
	arr := []int{1, 2, 3}
	var result [][]int
	permute(arr, 0, &result)
	fmt.Println(result)
}

A [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

B [[3 2 1] [3 1 2] [2 3 1] [2 1 3] [1 3 2] [1 2 3]]

C [[1 2 3] [2 1 3] [1 3 2] [3 1 2] [2 3 1] [3 2 1]]

D [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]

💡 Hint

Focus on the order in which the swapping happens and how the recursion explores permutations.

The code swaps elements starting from the current index and recursively generates permutations. The order of permutations is fixed by the swapping sequence, producing option D's output.

🧠 Conceptual

intermediate

Number of Permutations for an Array of Length N

If you have an array of length N, how many unique permutations can you generate?

A N

B N * (N-1)

C N!

D 2^N

💡 Hint

Think about how many choices you have for each position in the array.

The number of unique permutations of an array of length N is N factorial (N!). This is because for the first position you have N choices, for the second N-1, and so on.

🔧 Debug

advanced

Identify the Bug in Permutation Generation Code

What error does the following Go code produce when trying to generate permutations of [1, 2, 3]?

DSA Go

package main

import "fmt"

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

func main() {
	arr := []int{1, 2, 3}
	var result [][]int
	permute(arr, 0, &result)
	fmt.Println(result)
}

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

B Compilation error due to missing return statement.

C The output is empty because the base case is never reached.

D Runtime panic due to index out of range.

💡 Hint

Look at how the slice is appended to the result in the base case.

Appending the slice 'nums' directly stores references to the same underlying array. Later swaps modify all stored slices, making all permutations appear identical.

🚀 Application

advanced

Find the 4th Permutation of [1, 2, 3, 4]

Using lexicographic order, what is the 4th permutation of the array [1, 2, 3, 4]?

A [1 3 2 4]

B [1 3 4 2]

C [1 4 2 3]

D [2 1 3 4]

💡 Hint

List permutations in order starting from [1 2 3 4].

The lexicographic permutations start as: 1) [1 2 3 4], 2) [1 2 4 3], 3) [1 3 2 4], 4) [1 3 4 2].

📝 Syntax

expert

Identify the Syntax Error in Permutation Code Snippet

Which option contains the syntax error in this Go code snippet for generating permutations?

DSA Go

func permute(nums []int, start int, result *[][]int) {
	if start == len(nums)-1 {
		temp := make([]int, len(nums))
		copy(temp, nums)
		*result = append(*result, temp)
		return
	}
	for i := start; i < len(nums); i++ {
		nums[start], nums[i] = nums[i], nums[start]
		permute(nums, start+1, result)
		nums[start], nums[i] = nums[i], nums[start]
	}
}

A Missing closing brace '}' for the function.

B Incorrect use of copy function arguments order.

C Using *result = append(*result, temp) is invalid syntax.

D The for loop syntax is incorrect; missing semicolon.

💡 Hint

Check if all braces are properly closed.

Option A is correct because the code snippet is missing the final closing brace '}' for the function permute.

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