LeetCode 39. Combination Sum：回溯法找到解后为何需return？

一、未添加return导致重复结果的原因 #

当total == target时，你仅将当前组合加入结果列表，但没有终止当前递归分支。后续代码会执行到终止条件判断if i >= len(candidates) or total > target:——此时total等于target，不满足该条件，因此不会触发return。

接下来代码会继续执行后续逻辑：

• 先将当前元素追加到cur中，此时total + candidates[i]必然大于target，后续递归会直接触发终止条件返回，随后执行cur.pop()
• 接着调用backtrack(i + 1, cur, total)，这会在当前组合已经符合要求的前提下，继续递归遍历后续元素，导致同一组合被多次添加到结果列表中。

举个具体例子：当找到组合[2,2,3]时，未加return会继续执行跳过3、尝试6和7的递归分支，虽然这些分支不会产生新的有效组合，但原有效组合会在不同递归路径中被重复记录。添加return后，一旦找到符合条件的组合就直接终止当前分支，避免了后续不必要的递归，自然消除了重复结果。

二、排序剪枝的实现方式 #

首先对candidates数组进行升序排序，这样当递归中total + candidates[i] > target时，后续元素均大于当前元素，累加后必然也超过target，可直接终止当前分支，无需遍历后续元素。

方式一：基于for循环的回溯剪枝 #

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        # 先对数组升序排序
        candidates.sort()
        def backtrack(start, cur, total):
            if total == target:
                res.append(cur[:])
                return
            if total > target:
                return
            # 遍历从start开始的元素，实现可重复选取
            for i in range(start, len(candidates)):
                # 剪枝：当前元素累加后超过target，后续更大元素无需尝试
                if total + candidates[i] > target:
                    break
                cur.append(candidates[i])
                backtrack(i, cur, total + candidates[i])
                cur.pop()
        backtrack(0, [], 0)
        return res

方式二：保留原递归结构的剪枝 #

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def backtrack(i, cur, total):
            if total == target:
                res.append(cur[:])
                return
            if i >= len(candidates) or total > target:
                return
            # 剪枝：当前元素累加后超过target，直接终止后续递归
            if total + candidates[i] > target:
                return
            cur.append(candidates[i])
            backtrack(i, cur, total + candidates[i])
            cur.pop()
            backtrack(i + 1, cur, total)
        backtrack(0, [], 0)
        return res

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