LeetCode等分子集和问题递归逻辑下标差异疑问

两种写法都是正确的，核心区别是递归函数第二个参数的语义定义不同，本质逻辑完全一致。

两种写法的语义约定 #

• 题解递推式：isSum (subSetSum, n) = isSum(subSetSum- nums[n], n-1) || isSum(subSetSum, n-1)
  约定第二个参数n是当前待决策元素的数组下标，默认数组下标从0开始，初始调用时n取值为数组长度减1，直接取nums[n]就是当前要决策的元素。
• 示例代码递归逻辑：bool result = dfs(nums, n - 1, subSetSum - nums[n - 1]) || dfs(nums, n - 1, subSetSum);
  约定dfs的第二个参数是当前待处理的元素总个数，对应数组下标范围为0 ~ 第二个参数 - 1，初始调用时第二个参数取值为数组总长度，所以当前要决策的元素下标是n-1，需要减去nums[n-1]。

逻辑等价验证 #

我们以简单用例举例：数组nums = [1,2]，目标和为3，数组长度为2：

1. 按递推式约定调用：初始调用isSum(3, 1)（下标1对应元素2），选择元素2时递归调用isSum(3-2=1, 0)，后续处理下标0的元素1即可得到正确结果。
2. 按代码约定调用：初始调用dfs(nums, 2, 3)（待处理元素总数为2），当前要决策的元素下标为2-1=1对应元素2，选择元素2时递归调用dfs(nums, 1, 3-2=1)，后续处理待处理总数为1的元素即可得到正确结果。

你测试时两种写法都返回正确结果，是因为你调用递归函数时遵循了对应约定的初始传参规则，整个递归链路的下标取值是自洽的，自然不会出错。

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