如何生成唯一序列？LeetCode 377组合总和IV递归解法疑问

问题核心 #

你当前的代码是按「不考虑顺序的组合」思路写的，而377题要求的是「考虑顺序的序列」——比如(1,1,2)和(1,2,1)是两个不同的解，你的递归逻辑限制了只能从当前索引i往后选数，自然会漏掉这些不同顺序的情况。

修正你的DFS解法 #

要生成所有顺序不同的序列，递归时不需要固定起始索引i，每次都应该从数组的第一个元素开始尝试选择，只要当前总和加上该元素不超过target即可。

修正后的代码如下：

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        result = []
        def dfs(curr, total):
            if total == target:
                result.append(curr[::])
                return
            if total > target:
                return
            # 每次都从数组第一个元素开始遍历，而非从i开始
            for num in nums:
                curr.append(num)
                dfs(curr, total + num)
                curr.pop()

        dfs([], 0)
        print(result)
        return len(result)

这段代码会遍历所有可能的数字选择顺序，生成题目要求的7种序列。

不同场景的递归树构建思路 #

1. 唯一组合（顺序无关，如Combination Sum I） #

这类问题要求不同顺序的相同元素集合算一个解，递归树的构建需要避免重复选择同一组合的不同排列。

• 递归逻辑：每次从当前索引i开始遍历数组，选择当前元素后，下一层递归仍从i开始（允许重复选同一元素）；不选当前元素时，下一层递归从i+1开始（跳过当前元素，避免重复组合）。
• 递归树特点：每个分支代表是否选择当前索引的元素，确保同一组合只会被生成一次。
  示例代码（Combination Sum I风格）：

def combinationSum(nums, target):
    result = []
    def dfs(i, curr, total):
        if total == target:
            result.append(curr[::])
            return
        if total > target or i >= len(nums):
            return
        # 选当前元素，下一层仍从i开始（允许重复选）
        curr.append(nums[i])
        dfs(i, curr, total + nums[i])
        curr.pop()
        # 不选当前元素，下一层从i+1开始
        dfs(i+1, curr, total)
    dfs(0, [], 0)
    return result

2. 唯一序列（顺序相关，即本题） #

这类问题要求不同顺序的元素集合算不同解，递归树需要枚举所有可能的选择顺序。

• 递归逻辑：每次递归都从数组的第一个元素开始遍历，每个元素只要满足总和不超过target都可以被选择，下一层递归继续从数组开头重新选择。
• 递归树特点：每个分支代表选择数组中的某一个元素，所有可能的排列都会被遍历到，不会遗漏任何顺序的序列。

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