According to the above post (Permutations), I want to overwrite it in Go with his algorithm.
But there is a stack overflow error occurs.
Below is my code. Can help me solve this problem, 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
}
What's happening is an infinite recursion. That leads to stack overflows because the function return address and the function's arguments take stack space.
The problem comes from the loop: by the time the third level of recursion (the one that appends the 3) returns, it removed the 2 and the 3 from the slice. So the previous level, that should be finishing its second iteration, will see the 3 is missing, so it will call backtrack again, but that one will see the 3 is missing, but when it comes back the 2 and 3 are missing, so it will call backtrack recursively two more times, and so on and so on.