LeetCode78. Subsets回溯解法疑问：索引递减与元素弹出逻辑困惑

问题说明 #

给定一个元素唯一的整数数组nums，返回所有可能的子集。解集不能包含重复子集，返回顺序任意。

示例1：输入nums = [1,2,3]，输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

用户提供的DFS解法代码：

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        def dfs(index):
            if index >= len(nums):
                res.append(subset.copy())
                return
            
            subset.append(nums[index])
            dfs(index + 1)

            subset.pop()
            dfs(index + 1)
        dfs(0)
        return res

疑问1：索引达到数组长度后为何会“递减”？ #

这是递归调用栈的回溯特性导致的。当index >= len(nums)触发return时，程序并不会直接结束，而是回到上一层递归的调用位置，继续执行后续代码。

拿nums = [1,2,3]举例：

• 调用dfs(3)时，满足终止条件，把当前subset的副本加入结果，然后return。此时程序回到上一层——也就是dfs(2)中调用dfs(3)的位置（即subset.append(3)之后的那行dfs(index+1)）。
• 执行完return后，dfs(2)会继续往下执行subset.pop()，接着调用dfs(3)，再次触发终止条件return，随后dfs(2)执行完毕return，回到dfs(1)的对应位置……以此类推，每一层递归return后都会回到上一层，看起来就像“索引递减”，本质是递归栈的逐层回溯。

疑问2：添加元素到弹出元素的跳转逻辑 #

这段代码的核心是对每个元素做两种选择：选它，或者不选它，递归和回溯就是实现这两种选择的关键：

1. 选择当前元素：执行subset.append(nums[index])，然后递归调用dfs(index+1)——带着当前元素，继续处理下一个元素。
2. 回溯（撤销选择）：当上面的递归调用完成并return后，程序回到dfs(index+1)的下一行，执行subset.pop()——把刚才添加的元素从subset中移除，回到选择当前元素之前的状态。
3. 不选当前元素：接着调用dfs(index+1)——不带着当前元素，继续处理下一个元素。

用初始步骤举例：

• 第一次调用dfs(0)，先执行subset.append(1)，然后调用dfs(1)。
• 在dfs(1)中，执行subset.append(2)，调用dfs(2)。
• 在dfs(2)中，执行subset.append(3)，调用dfs(3)。
• dfs(3)触发终止条件，把[1,2,3]加入结果，return回到dfs(2)。
• dfs(2)执行subset.pop()，subset变回[1,2]，然后调用dfs(3)，触发终止条件，把[1,2]加入结果，return回到dfs(2)，dfs(2)执行完毕return回到dfs(1)。
• dfs(1)执行subset.pop()，subset变回[1]，调用dfs(2)……以此类推，遍历所有选择分支后，就能得到所有子集。

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