Generate All Permutations of Array in DSA Go

Mental Model

We want to list every possible order of the items in the array by swapping elements step by step.

Analogy: Imagine you have a set of colored balls and want to see all ways to line them up on a shelf by swapping their places.

[1, 2, 3]
↑
We start with the first position and try all numbers here.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: List all possible orders of the array elements.

Step 1: Start at index 0, swap element at 0 with 0 (no change), fix 1 at first position

[1, 2, 3] ↑ index=0

Why: We begin by fixing the first element and permute the rest.

Step 2: Move to index 1, swap element at 1 with 1 (no change), fix 2 at second position

[1, 2, 3] ↑ index=1

Why: Fix second element and permute the last element.

Step 3: Move to index 2, swap element at 2 with 2 (no change), fix 3 at third position

[1, 2, 3] ↑ index=2

Why: Last element fixed, record permutation [1, 2, 3].

Step 4: Backtrack to index 1, swap element at 1 with 2, swap 2 and 3

[1, 3, 2] ↑ index=1

Why: Try next option for second position.

Step 5: Move to index 2, swap element at 2 with 2 (no change), fix 2 at third position

[1, 3, 2] ↑ index=2

Why: Last element fixed, record permutation [1, 3, 2].

Step 6: Backtrack to index 0, swap element at 0 with 1, swap 1 and 2

[2, 1, 3] ↑ index=0

Why: Try next option for first position.

Step 7: Move to index 1, swap element at 1 with 1 (no change), fix 1 at second position

[2, 1, 3] ↑ index=1

Why: Fix second element and permute the last element.

Step 8: Move to index 2, swap element at 2 with 2 (no change), fix 3 at third position

[2, 1, 3] ↑ index=2

Why: Last element fixed, record permutation [2, 1, 3].

Result:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func permute(nums []int) [][]int {
	var res [][]int
	var backtrack func(int)
	backtrack = func(start int) {
		if start == len(nums) {
			// Make a copy of nums and add to results
			tmp := make([]int, len(nums))
			copy(tmp, nums)
			res = append(res, tmp)
			return
		}
		for i := start; i < len(nums); i++ {
			// Swap to fix element at start
			nums[start], nums[i] = nums[i], nums[start]
			backtrack(start + 1) // Recurse for next position
			// Swap back to restore original order
			nums[start], nums[i] = nums[i], nums[start]
		}
	}
	backtrack(0)
	return res
}

func main() {
	input := []int{1, 2, 3}
	result := permute(input)
	for _, perm := range result {
		fmt.Println(perm)
	}
}

if start == len(nums) {

Reached end of array, record current permutation

nums[start], nums[i] = nums[i], nums[start]

Swap to fix element at current position

backtrack(start + 1)

Recurse to fix next position

nums[start], nums[i] = nums[i], nums[start]

Swap back to restore original order for next iteration

Output

[1 2 3]

[1 3 2]

[2 1 3]

[2 3 1]

[3 2 1]

[3 1 2]

Complexity Analysis

Time: O(n! * n) because there are n! permutations and copying each permutation takes O(n)

Space: O(n) for recursion stack plus O(n! * n) for storing all permutations

vs Alternative: This backtracking approach is efficient compared to generating permutations by inserting elements into all positions repeatedly, which is more complex to implement and less direct.

Edge Cases

empty array

returns a list with one empty permutation

DSA Go

if start == len(nums) {

array with one element

returns a list with one permutation containing that element

DSA Go

if start == len(nums) {

array with duplicate elements

returns permutations including duplicates since no duplicate check is implemented

DSA Go

no specific guard for duplicates

When to Use This Pattern

When you need to list all possible orders of a set of items, use backtracking with swapping to generate permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursive call, causing wrong permutations
Fix: Always swap back to restore original order after recursion

Mistake: Copying the original array reference instead of making a copy when recording permutations
Fix: Make a new copy of the array before appending to results

Summary

Generates all possible orders (permutations) of the array elements.

Use when you want to explore every arrangement of items in a list.

Fix one element at a time by swapping, then recurse to fix the next.

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