LeetCode77组合问题：Golang递归算法遇栈溢出（测试(3,2)出错）

问题描述 #

我在使用Golang实现LeetCode77组合问题的递归算法时，遇到了栈溢出问题，即使测试小规模输入(3,2)也会触发该问题。我的代码如下：

package main

import (
    "fmt"
)

func combine1(n int, k int) [][]int {
    res := [][]int{}
    if k == 1 {
        for i := 1; i <= n; i++ {
            res = append(res, []int{i})
        }
        return res
    }
    //The k number contains the combination of digits n
    for _, combination := range combine1(n-1, k-1) {
        combination = append(combination, n)
        res = append(res, combination)
    }
    //The k number does not contain the combination of the number n
    for _, combination := range combine1(n-1, k) {
        res = append(res, combination)
    }
    return res
}

func main() {
    fmt.Println("运行")
    
    fmt.Println(combine1(3,2))
}

我已多次检查代码和逻辑，似乎都没有问题，请问问题出在哪里？

问题原因 #

你的递归函数缺少关键的终止条件：当k > n（需要选择的元素数量超过总元素数量）或者k == 0（不需要选择任何元素）时，没有定义递归终止的逻辑，导致无限递归调用，最终触发栈溢出。

以输入(3,2)为例，递归过程中会调用combine1(2,2)，而combine1(2,2)又会调用combine1(1,2)——此时k=2 > n=1，但你的代码没有处理这种情况，会继续递归调用combine1(0,1)和combine1(0,2)，后续还会生成n为负数的递归调用，循环往复直到栈被撑爆。

修复方案 #

添加两个必要的终止条件：

1. 当k == 0时，返回包含空切片的切片（选0个元素的组合只有空组合）
2. 当k > n时，返回空切片（不可能从n个元素中选出k个元素）

修复后的代码如下：

package main

import (
    "fmt"
)

func combine1(n int, k int) [][]int {
    res := [][]int{}
    // 终止条件1：选0个元素，返回空组合
    if k == 0 {
        return [][]int{{}}
    }
    // 终止条件2：k大于n，无有效组合
    if k > n {
        return res
    }
    if k == 1 {
        for i := 1; i <= n; i++ {
            res = append(res, []int{i})
        }
        return res
    }
    // 包含n的组合：从n-1个元素选k-1个，再追加n
    for _, combination := range combine1(n-1, k-1) {
        combination = append(combination, n)
        res = append(res, combination)
    }
    // 不包含n的组合：从n-1个元素选k个
    for _, combination := range combine1(n-1, k) {
        res = append(res, combination)
    }
    return res
}

func main() {
    fmt.Println("运行")
    fmt.Println(combine1(3,2)) // 输出 [[1 3] [2 3] [1 2]]
}

补充说明 #

你原来的递归逻辑是正确的（分包含n和不包含n两种情况），但递归函数必须覆盖所有可能的边界情况，否则就会出现无限递归的问题。添加这两个终止条件后，递归会在遇到无效情况时及时停止，避免栈溢出。

内容的提问来源于stack exchange，提问作者Richard Dimon