LeetCode 排列 - 堆栈溢出错误

Question

https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

根据上面的post(Permutations)，我想用他的算法在Go中覆盖

但是出现栈溢出错误

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

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
}

Answer 1

发生的是无限递归。这导致堆栈溢出，因为函数 return 地址和函数的参数占用堆栈 space.

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

LeetCode 排列 - 堆栈溢出错误

LeetCode Permutations - Stack overflow error

stack-overflow

permutation

go