LeetCode 排列 - 堆栈溢出错误

最近发现不少小伙伴都对Golang很感兴趣，所以今天继续给大家介绍Golang相关的知识，本文《LeetCode 排列 - 堆栈溢出错误》主要内容涉及到等等知识点，希望能帮到你！当然如果阅读本文时存在不同想法，可以在评论中表达，但是请勿使用过激的措辞~

https://leetcode.com/problems/permutations/discuss/18239/a-general-approach-to-backtracking-questions-in-java-(subsets-permutations-combination-sum-palindrome-partioning) p>

根据上面的帖子（permutations），我想用他的算法在 go 中覆盖它。

但是出现了堆栈溢出错误。

下面是我的代码。可以帮我解决这个问题，谢谢。

package main

import (
    "fmt"
)

func main() {
    nums := []int{1, 2, 3}
    ans := permute(nums)
    fmt.Println(ans)
}

func permute(nums []int) [][]int {
    result := make([][]int, 0)
    tempAry := make([]int, 0)
    backtrack(&result, tempAry, nums)
    return result
}

func backtrack(result *[][]int, temp []int, nums []int) {
    if len(nums) == len(temp) {
        *result = append(*result, temp)
    } else {
        for i := 0; i < len(nums); i++ {
            if binarySearch(nums[i], temp) != -1 {
                continue
            } else {
                temp = append(temp, nums[i])
                backtrack(result, temp, nums)
                temp2 := temp[0 : len(temp)-2]
                temp = temp2
            }
        }
    }
}

func binarySearch(target int, array []int) int {
    low := 0
    high := len(array) - 1
    for high > low {
        mid := (high + low) / 2
        if array[mid] > target {
            high = mid - 1

        } else if array[mid] < target {
            low = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

解决方案

发生的是无限递归。这会导致堆栈溢出，因为函数返回地址和函数的参数占用堆栈空间。

问题来自于循环：当第三级递归（附加 3 的递归）返回时，它从切片中删除了 2 和 3。因此，上一个级别（应该完成第二次迭代）将看到 3 丢失，因此它将再次调用 backtrack，但是该级别会看到 3 丢失，但当它返回时，2 和 3 丢失，所以它将再递归调用 backtrack 两次，依此类推。

理论要掌握，实操不能落！以上关于《LeetCode 排列 - 堆栈溢出错误》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！