如何在回溯类问题中递归实现选择逻辑？

你的现有代码存在问题：循环里每次固定选择toChoose[0]，还直接修改toChoose切片，导致无法遍历所有可选元素，最终只能生成一种排列。要实现全排列的“选择”逻辑，核心是遍历所有当前可选元素，选一个后递归处理剩余元素，递归返回后撤销选择（回溯），再尝试下一个元素。

修正后的代码 #

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 {
            // 1. 做选择：把当前第i个元素加入临时路径
            tmp = append(tmp, toChoose[i])
            // 2. 生成剩余可选元素：创建新切片，排除已选的第i个元素
            remaining := append(append([]int{}, toChoose[:i]...), toChoose[i+1:]...)
            // 3. 递归深入：处理剩余元素，为下一个位置做选择
            helper(remaining)
            // 4. 回溯：撤销刚才的选择，让临时路径回到之前的状态
            tmp = tmp[:len(tmp)-1]
        }
    }

    helper(nums)
    return res
}

关键逻辑拆解 #

以输入[1,2]为例，走一遍完整流程，理解每一步的选择与回溯：

1. 初始调用helper([1,2])，tmp为空。
2. 循环i=0：
   • 选择1加入tmp，tmp变为[1]。
   • 剩余元素是[2]，调用helper([2])。
     • 在helper([2])中，循环i=0：
       • 选择2加入tmp，tmp变为[1,2]。
       • 剩余元素为空，将[1,2]加入res，返回。
     • 回溯：tmp截断为[1]。
3. 循环i=1：
   • 选择2加入tmp，tmp变为[2]。
   • 剩余元素是[1]，调用helper([1])。
     • 在helper([1])中，循环i=0：
       • 选择1加入tmp，tmp变为[2,1]。
       • 剩余元素为空，将[2,1]加入res，返回。
     • 回溯：tmp截断为[2]。
4. 回溯：tmp截断为空，循环结束，最终res包含[[1,2],[2,1]]。

核心思想 #

递归回溯的“选择”逻辑本质是穷举所有可能的路径：

• 每一层递归对应排列的一个位置，我们要为这个位置选择所有可能的元素。
• 选完一个元素后，递归处理下一个位置（剩余元素）。
• 递归返回后必须撤销选择（回溯），这样才能回到当前层，尝试选择其他元素，遍历所有分支。

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