Solving the LeetCode "Permutations" Problem in Go

Difficulty: Medium | Tags: Array, Backtracking

Introduction

Generating all permutations of a given array is a classic problem in computer science, often used to test understanding of recursion and backtracking. This problem requires returning all possible orderings of distinct integers in an array.

Problem Analysis

Given an array of distinct integers, the task is to generate all possible permutations. For example, for the input [1,2,3], the output should include all 6 possible orderings. The constraints ensure the input size is manageable, making backtracking a viable solution.

Solution Approach

The solution involves using backtracking to explore all possible permutations. We swap elements in the array to generate different orderings and backtrack to explore other possibilities. This approach efficiently explores the solution space without redundancy.

Go Implementation

func permute(nums []int) [][]int {
    var result [][]int
    backtrack(nums, 0, &result)
    return result
}
func backtrack(nums []int, start int, result *[][]int) {
    if start == len(nums) {
        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]
        backtrack(nums, start+1, result)
        nums[start], nums[i] = nums[i], nums[start]
    }
}

Complexity Analysis

Time Complexity: O(N!), where N is the number of elements in the array. This is because there are N! permutations for an array of size N.

Space Complexity: O(N!), as we store all permutations in the result. The recursion stack depth is O(N), but the dominant factor is the output storage.

Testing and Examples

Test cases include:

• nums = [1,2,3] → 6 permutations
• nums = [0,1] → 2 permutations
• nums = [1] → 1 permutation

Best Practices and Tips

When implementing backtracking, ensure you undo changes (like swaps) after recursive calls to maintain the array's state. Use slices carefully in Go to avoid unintended modifications. For larger inputs, consider iterative approaches if recursion depth is a concern.