递归求解回溯问题的方法和实现

小伙伴们有没有觉得学习Golang很有意思？有意思就对了！今天就给大家带来《递归求解回溯问题的方法和实现》，以下内容将会涉及到，若是在学习中对其中部分知识点有疑问，或许看了本文就能帮到你！

我无法理解如何在递归回溯问题中实现“选择”。

我有以下代码用于查找给定 int 切片的所有排列：

func permute(nums []int) [][]int {
    res := [][]int{}
    tmp := []int{}

    var helper func( []int)
    helper = func(toChoose []int) {
        if len(toChoose) == 0{
            cp := make([]int, len(tmp))
            copy(cp, tmp)
            res = append(res, cp)
            return
        }

        for i, _ := range toChoose{ 
            tmp = append(tmp, toChoose[0])
            toChoose = toChoose[1:]
            helper(toChoose)
        }
    }

    helper(nums)
    return res
}

基本上据我了解，在结果数组之一的每个槽中，我需要决定从输入中选择一个数字，例如：

输入：[1, 2]

对于槽 0，选择索引 1 或 0

对于槽 1，选择保留的索引

我们得到结果： [1, 2], [2, 1]

我怎样才能递归地执行这个“决定”？我想这是我充分理解回溯和递归的关键。

正确答案

您可以尝试使用下一个排列算法。查看this文章。这并不完全是为 Golang 编写的，但想法是相同的。基本上，给定一个数组，下一个排列会对数组执行一些交换操作，并给出下一个排列。因此，如果给它们一个 [1,2,3] 数组，则下一个排列将是 [1,3,2]，然后下一个排列将是 [2,1,3] ，然后是 [2,3,1]，然后是 [3,1,2]，然后是 [3,2,1]。您可以一遍又一遍地调用 next permutation 来列出所有可能的排列。

在 C++ 中，我们的标准库中有此算法。对于Golang，我想你可以查看this。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《递归求解回溯问题的方法和实现》文章吧，也可关注golang学习网公众号了解相关技术文章。