Перестановки в LeetCode - ошибка переполнения стека - PullRequest
Новая
       72

Перестановки в LeetCode - ошибка переполнения стека

0 голосов
/ 04 апреля 2020

https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java- (Подмножества-Перестановки-Комбинация-Сумма-Палиндром-Разделение)

В соответствии с приведенным выше постом (Перестановки) я хочу перезаписать его в 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
}

1 Ответ

0 голосов
/ 04 апреля 2020

То, что происходит, - это бесконечная рекурсия. Это приводит к переполнению стека, поскольку адрес возврата функции и аргументы функции занимают место в стеке.

Проблема возникает из-за l oop: ко времени третьего уровня рекурсии (тот, который добавляет 3) возвращается, он удалил 2 и 3 из среза. Таким образом, предыдущий уровень, который должен завершить свою вторую итерацию, увидит, что 3 отсутствует, поэтому он снова вызовет backtrack, но тот увидит, что 3 отсутствует, но когда он вернется, 2 и 3 отсутствуют , поэтому он будет вызывать backtrack рекурсивно еще два раза, и так далее, и так далее.

...