Generate all permutations in go

Go programming

permutations

algorithms

coding tutorials

combinatorics

Generate all permutations in go

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms Math for Programmers

Introduction

Generating permutations is a classic combinatorics problem and a common interview topic in Go. The practical challenge is not only correctness, but also writing code that avoids accidental slice mutation and unnecessary allocations. A solid backtracking implementation is usually the best starting point.

What a Permutation Generator Must Guarantee

Given n unique elements, a permutation generator should return exactly n! arrangements, each containing every element once. For input with duplicates, you often need a deduplication strategy to avoid repeated output.

Performance matters quickly. Even at n = 10, the count is 3,628,800 permutations. In real systems, you usually stream results, limit output, or run the algorithm only for small sets.

Backtracking Implementation in Go

This approach builds permutations incrementally. A used array tracks which items are already in the current path.

1package main
2
3import "fmt"
4
5func permute(nums []int) [][]int {
6    result := make([][]int, 0)
7    path := make([]int, 0, len(nums))
8    used := make([]bool, len(nums))
9
10    var dfs func()
11    dfs = func() {
12        if len(path) == len(nums) {
13            clone := make([]int, len(path))
14            copy(clone, path)
15            result = append(result, clone)
16            return
17        }
18
19        for i := 0; i < len(nums); i++ {
20            if used[i] {
21                continue
22            }
23            used[i] = true
24            path = append(path, nums[i])
25            dfs()
26            path = path[:len(path)-1]
27            used[i] = false
28        }
29    }
30
31    dfs()
32    return result
33}
34
35func main() {
36    nums := []int{1, 2, 3}
37    perms := permute(nums)
38    for _, p := range perms {
39        fmt.Println(p)
40    }
41}

The critical detail is cloning path before appending to result. Without cloning, all rows can point to the same backing array and final output becomes incorrect.

In Place Swap Variant

An alternative uses swaps inside a single slice. This can reduce extra state and often runs fast in Go.

1package main
2
3import "fmt"
4
5func permuteInPlace(nums []int) [][]int {
6    out := make([][]int, 0)
7
8    var generate func(int)
9    generate = func(start int) {
10        if start == len(nums) {
11            clone := make([]int, len(nums))
12            copy(clone, nums)
13            out = append(out, clone)
14            return
15        }
16
17        for i := start; i < len(nums); i++ {
18            nums[start], nums[i] = nums[i], nums[start]
19            generate(start + 1)
20            nums[start], nums[i] = nums[i], nums[start]
21        }
22    }
23
24    generate(0)
25    return out
26}
27
28func main() {
29    nums := []int{1, 2, 3}
30    for _, p := range permuteInPlace(nums) {
31        fmt.Println(p)
32    }
33}

This version mutates input while searching, then restores it by swapping back. If callers need the input untouched, pass a copy.

Handling Duplicate Values

If input may contain duplicates, sort first and skip repeated choices at the same depth.

1package main
2
3import (
4    "fmt"
5    "sort"
6)
7
8func permuteUnique(nums []int) [][]int {
9    sort.Ints(nums)
10
11    result := make([][]int, 0)
12    path := make([]int, 0, len(nums))
13    used := make([]bool, len(nums))
14
15    var dfs func()
16    dfs = func() {
17        if len(path) == len(nums) {
18            clone := append([]int(nil), path...)
19            result = append(result, clone)
20            return
21        }
22
23        for i := 0; i < len(nums); i++ {
24            if used[i] {
25                continue
26            }
27            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
28                continue
29            }
30
31            used[i] = true
32            path = append(path, nums[i])
33            dfs()
34            path = path[:len(path)-1]
35            used[i] = false
36        }
37    }
38
39    dfs()
40    return result
41}
42
43func main() {
44    fmt.Println(permuteUnique([]int{1, 1, 2}))
45}

The duplicate skip rule depends on sorted order and previous index usage state.

Practical Usage Guidance

In production, avoid materializing huge permutation sets in memory. Prefer a callback style generator so each permutation can be consumed immediately.

1func forEachPermutation(nums []int, visit func([]int) bool) {
2    used := make([]bool, len(nums))
3    path := make([]int, 0, len(nums))
4
5    var dfs func() bool
6    dfs = func() bool {
7        if len(path) == len(nums) {
8            clone := append([]int(nil), path...)
9            return visit(clone)
10        }
11        for i := range nums {
12            if used[i] {
13                continue
14            }
15            used[i] = true
16            path = append(path, nums[i])
17            if !dfs() {
18                return false
19            }
20            path = path[:len(path)-1]
21            used[i] = false
22        }
23        return true
24    }
25
26    dfs()
27}

Returning false from visit allows early stop when you only need a subset.

Common Pitfalls

Appending the same path slice to results without cloning, which corrupts output.
Forgetting to restore state during backtracking, such as not resetting used or not swapping back.
Generating duplicates for repeated input values because skip logic is missing.
Allocating very large result slices for high n, causing memory spikes.
Ignoring factorial growth and trying to generate full permutations for large inputs in request path code.

Summary

Backtracking with used flags is clear, correct, and easy to maintain.
In place swap generation is compact and efficient when mutation is acceptable.
Duplicate handling needs sorted input and depth aware skip rules.
Clone slices before storing results to avoid shared backing array bugs.
Prefer streaming or early stop patterns for realistic workloads.

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Generate all permutations in go

Data Structures & Algorithms practice on Codemia

Introduction

What a Permutation Generator Must Guarantee

Backtracking Implementation in Go

In Place Swap Variant

Handling Duplicate Values

Practical Usage Guidance

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia