LeetCode如何解决组合总和问题

# 1. 问题背景

组合总和问题是一个经典的回溯问题，在 LeetCode 上有多道相关的题目，涉及到不同的元素组合、目标值等。给定一个数组和一个目标数，找出数组中所有可以使数字和等于目标数的组合。同一个数字可能会被选取多次。

例如，给定 candidates = [2, 3, 6, 7] 和 target = 7，一个可能的解为:

[
  [7],
  [2, 2, 3]
]

要解决组合总和问题，可以使用回溯算法。回溯算法可以理解为一种深度优先搜索的遍历算法，用于在一个问题的解空间中寻找所有可能的解。具体思路如下：

步骤 1：首先对输入数组进行排序，以便在回溯过程中可以方便地进行剪枝操作。

步骤 2：定义一个递归函数 backtrack，它接收一个当前位置信息 index 和一个当前路径 combination 作为参数。

步骤 3：在每一轮递归中，首先判断当前路径 combination 的和是否等于目标值 target。如果等于目标值，将当前路径 combination 保存下来。

步骤 4：然后，从当前位置 index 开始，遍历数组 candidates。对于每个元素，如果当前路径 combination 的和加上该元素不超过目标值 target，就将该元素加入到当前路径 combination 中，并调用 backtrack 总下一层递归。

步骤 5：递归回溯时，将刚刚加入的元素从当前路径 combination 中移除，以便尝试其他路径。

步骤 6：在回溯过程中，可以通过剪枝操作，避免重复计算，提高效率。具体剪枝操作为，在遍历 candidates 数组时，如果当前元素小于目标值 target，就跳过该元素。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()  # 排序
        res = []
        
        def backtrack(index, combination, cur_sum):
            if cur_sum == target:
                res.append(combination)
                return
            for i in range(index, len(candidates)):
                if cur_sum + candidates[i] > target:
                    break
                backtrack(i, combination + [candidates[i]], cur_sum + candidates[i])
        
        backtrack(0, [], 0)
        return res

通过以上的算法思路和实现代码，可以解决组合总和问题。在 LeetCode 上有多道类似的题目，例如组合总和 II、组合总和 III 等，只需要稍作修改即可应用同样的算法。