【回溯法】——组合总数

回溯核心思想

• 回溯算法的关键在于：不合适就退回到上一步
• 具体的：通过枚举法，对所有可能性进行遍历，枚举顺序是一条路走到黑，走到头满足条件后，退一步，再尝试之前没走过的路，直到所有路都走了。

回溯关键点

• 一条路走到黑
• 回退一步
• 另寻他路

实现

• for循环：

  • 另寻他路：用for循环实现一个路径选择器
  • 逐个选择当前节点下的所有可能往下走的分支路径
  • 例如：走到节点a，向下有i条路，用for循环将这i条路逐个尝试一遍。（进入每条路后递归，重复这个过程）

• 递归：

  • 一条路走到黑：把递归放在for循环内部，那么for每次循环都在给出一个路径之后进入递归，也就是继续向下走了
  • 回退一步：直到递归出口（无路可走）为止，那么从递归出口出来就会实现回退一步。

• for循环与递归配合就可以实现回溯：

  • 当递归从递归出口出来后
  • 上一层的for循环就会继续执行
  • 而for循环继续执行就是给出了当前节点的下一条可行路径
  • 而后递归调用，顺着这条从未走过的路径又向下走一步，这就是回溯

def backtracking():# 定义回溯点if （回溯点）:  # 这条路走到底了（保存该结果）returnelse:# 逐步选择当前节点下的所有可能路径for route in all_route_set: if （剪枝条件）: # 发现当前路不行（剪枝前的操作）return # 不继续往下走了，退回上层，换条路走else:  # 当前路径可行（保存当前数据）  # 向下走之前要记住已经走过了这个节点。保存（调用递归）self.backtracking(xx)  # 递归发生，继续向下走（回溯清理）  # 该节点下的路径都走完了！                        

• 剪枝：
  • 对于某些问题，走着走着发现这条路不通，再走也是浪费时间和内存
  • 所以直接退回去，切掉这条路

39. 组合总数

39. 组合总和

一、题目难度

中等

二、相关标签与相关企业

[相关标签]
[相关企业]

三、题目描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于150个。

四、示例

示例1

输入：

candidates = [2, 3, 6, 7]
target = 7

输出：

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

解释：
2和3可以形成一组候选，2 + 2 + 3 = 7。注意2可以使用多次。
7也是一个候选，7 = 7。
仅有这两种组合。

示例2

输入：

candidates = [2, 3, 5]
target = 8

输出：

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

示例3

输入：

candidates = [2]
target = 1

输出：

[]

五、提示

1. 1 <= candidates.length <= 30
2. 2 <= candidates[i] <= 40
3. candidates 的所有元素互不相同
4. 1 <= target <= 40

思路

1. 解空间：

• 由输入无重复元素的整数数组candidates=[xxxx]和目标整数target寻找使数字和为目标数的所有不同组合path，result
• 同一个数字candidates[i]可以被无限制重复选取

2. 定义回溯函数参数与终止条件

• 参数：
  • 输入：无重复元素的整数数组candidates=[xxxx]和目标整数target
  • 可行结果：path
  • 最终结果：result
  • 当前节点：start
• 核心思想：
  • 不断尝试当前节点可能的路径，将当前节点可走的路径都尝试后，向后移动start ，更新节点位置。（这里不涉及回溯）
  • 回溯的含义是：找到了一条path后，把当前的path末尾的值吐出来，相当于往后退一步，再尝试其他的。
  • 所以这道题回溯点就是“找到了一条路”：当前path满足sum(path) == target。实际代码实现可能涉及直接动target，不一定非这样写！
  • 涉及剪枝：比如某条路，才走了一点，就发现此路不通！某两个节点相加后直接大于了target，那么就没有必要继续走这条路了，直接去掉这个值

3. 具体代码实现步骤：

• 再看回溯算法模板，一步步根据这道题背景把代码步骤填进去

def backtracking():# 定义回溯点if （回溯点）:  # 这条路走到底了（保存该结果）returnelse:# 逐步选择当前节点下的所有可能路径for route in all_route_set: if （剪枝条件）: # 发现当前路不行（剪枝前的操作）return # 不继续往下走了，退回上层，换条路走else:  # 当前路径可行（保存当前数据）  # 向下走之前要记住已经走过了这个节点。保存（调用递归）self.backtracking(xx)  # 递归发生，继续向下走（回溯清理）  # 该节点下的路径都走完了！                        

• 本题基本机制：target = target - candidates[i]
  • 不断递归，回溯检查target
  • target == 0：走到头，得到一条path，放入result后，回溯，即删掉path最后一个值
  • target < 0: 剪枝
• 特解：空集candidates，则无结果，return []
• 初始化回溯函数的参数：
  • 输入：无重复元素的整数数组candidates=[xxxx]和目标整数target
  • 可行结果：path = []
  • 最终结果：result = []
  • 当前节点：start = 0
  • 将candidates[i]按照从小到大排列好:candidates.sort()
• 回溯函数：

  • 先定义回溯点：

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:if len(candidates) == 0:return []candidates.sort()path = []res = []'''！！！重点！！！在python中，如果传参是mutable var, 那么传参相当于引用，因此调用后，如果调用函数的内部对该传入变量进行修改，就会导致直接改变原始对象。这就是典型的privacy leak！！发生了。例如在这个，list就是该mutable var，而如果以path或res 为传参，放在__DFS 中， 那么就相当于在__DFS内部，实际上用的都是一个物理地址下的res和path，类似于全局变量。因此combinationSum下的局部变量path和res也在——DFS运行的过程中发生了改变。利用这个性质，我们可以把mutable var当成传入参数，从而实现全局变量的效果。'''self.__DFS(candidates, target, 0, path, res)return res'''DFS的实现'''def __DFS(self, candidates, target, begin, path, res):path = path.copy()# 递归出口 就是余数为0if target == 0:res.append(path)   #记录该符合条件的结果return#若当前路径有可能可行。for i in range(begin, len(candidates)):  # 我们现在到begin的节点上了if target - candidates[i] < 0:  # 剪枝条件return                      # 如果当前节点就不行了，就不用继续了,这里到不用继续了即包括该depth不用继续了，也包括该节点更大到child也不用继续了，该节点pop出来path.append(candidates[i])  #记录当前为止self.__DFS(candidates, target - candidates[i], i, path, res)# 向下继续走，记住递归不是return，递归到实现是调用！一旦return发生，递归停止。path.pop()  # 回朔清理。当前节点下的所有情况都进行完了，该节点也不应该在path里面了。

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:"""主函数，用于调用深度优先搜索（DFS），回溯来解决组合问题，并且返回最终结果:param candidates: 无重复元素的整数数组，从中选取数字组成满足条件target的组合:param target: 目标整数，要使得选取的数字组合的加和达到的值:return: 满足条件的所有不同组合的列表，每个组合都是一个整数列表"""# 特解：candidates空集：if len(candidates) == 0:  # 写成 not candidates 可以么？return []# 对候选数组candidates进行预先排序，方便后续剪枝操作candidates.sort()# 准备回溯函数的参数path = []    # 记录当前正在生成的一种数字组合情况，初始是空列表result = []  # 存储最终所有满足条件的数字组合，初始是空列表# 调用DFS开始回溯过程self.__DFS(candidates, target, 0, path, result)return result# 双下划线约定为“私有”方法，表示类的外部代码不应该直接调用这个函数def __DFS(self, condidates: List[int], target: int, begin: int, path: List[int], result: List[List[int]]):"""深度优先搜索（DFS）函数，用DFS实现回溯算法找出满足条件的数字组合"""# 先对path(上次递归得到的一条路)进行拷贝，# 避免后续操作中直接修改传入的path对象# （因为python中列表是可变对象，传参时可能出现意外修改情况）path = path.copy()# 设置递归出口：当目标值target==0# 说明当前path中的数字组合已经满足和为目标值的条件# 找到了一种满足条件的组合if target == 0:result.append(path)  # 存储path到resultreturn               # 回到上个节点# 遍历从begin位置开始的condidates中的元素# 逐个尝试作为组合的一部分for i in range(begin, len(candidates)):# 剪枝：如果当前值特别大，走到这个值的时候，直接超过了target# 即，target - candidates[i] < 0# 此路不通！return！if target - candidates[i] < 0:return # 否则，将当前数值candidates[i]添加到path，记录正在尝试的组合情况path.append(candidates[i])# 添加后，相当于走到了下一个岔路口# 此时调用递归继续向下一层搜索！ # path和result保持不变# 关键点在于，更新目标值为target-candidates[i]，表示剩余还需要凑的目标值# 本题更关键的！！！更新begin为i，# 因为candidates[i]可以被重复选择！！！所以暂时不要跳到下一个i+1！！！self.__DFS(candidates, target - candidates[i], i, path, res)# 当下一层递归返回后，说明当前节点下的所有（可重复选）# 可能情况都已经探索完成# 将path的最后一个元素弹出，恢复到添加该元素之前的状态，# 以便尝试下一个数字作为组合的一部分# 继续生成其他可能的满足条件的数字组合path.pop()
————————————————————————————————————————————
执行出错
AttributeError: 'Solution' object has no attribute '_Solution__DFS'^^^^^^^^^^self.__DFS(candidates, target, 0, path, result)
Line 22 in combinationSum (Solution.py)^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ret = Solution().combinationSum(param_1, param_2)
Line 105 in _driver (Solution.py)_driver()
Line 120 in <module> (Solution.py)

这里的错误主要在于内部方法 __DFS 的定义位置和调用方式。

错误分析

在Python中，当你在类的方法内部定义另一个方法时，这样的内部方法不能像你代码中那样直接在类的其他方法中调用。你把 __DFS 方法定义在了 combinationSum 方法内部，这导致在 combinationSum 尝试调用 __DFS 时，Python无法正确识别这个方法，从而报出 'Solution' object has no attribute '_Solution__DFS' 的错误，意思是 Solution 类的实例没有名为 _Solution__DFS 的属性（方法在Python中也被视为属性）。

修正建议

要解决这个问题，你需要把 __DFS 方法定义在和 combinationSum 方法平级的位置，也就是都作为 Solution 类的直接方法，如下所示：

from typing import Listclass Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:"""主函数，用于调用深度优先搜索（DFS），回溯来解决组合问题，并且返回最终结果:param candidates: 无重复元素的整数数组，从中选取数字组成满足条件target的组合:param target: 目标整数，要使得选取的数字组合的加和达到的值:return: 满足条件的所有不同组合的列表，每个组合都是一个整数列表"""# 特解：candidates空集：if len(candidates) == 0:  # 写成 not candidates 可以么？ 可以的，not candidates在candidates为空列表时会返回True，效果相同return []# 对候选数组candidates进行预先排序，方便后续剪枝操作candidates.sort()# 准备回溯函数的参数path = []    # 记录当前正在生成的一种数字组合情况，初始是空列表result = []  # 存储最终所有满足条件的数字组合，初始是空列表# 调用DFS开始回溯过程self.__DFS(candidates, target, 0, path, result)return resultdef __DFS(self, candidates: List[int], target: int, begin: int, path: List[int], result: List[List[int]]):"""深度优先搜索（DFS）函数，用DFS实现回溯算法找出满足条件的数字组合"""# 先对path(上次递归得到的一条路)进行拷贝，# 避免后续操作中直接修改传入的path对象# （因为python中列表是可变对象，传参时可能出现意外修改情况）path = path.copy()# 设置递归出口：当目标值target==0# 说明当前path中的数字组合已经满足和为目标值的条件# 找到了一种满足条件的组合if target == 0:result.append(path)  # 存储path到resultreturn               # 回到上个节点# 遍历从begin位置开始的candidates中的元素# 逐个尝试作为组合的一部分for i in range(begin, len(candidates)):# 剪枝：如果当前值特别大，走到这个值的时候，直接超过了target# 即，target - candidates[i] < 0# 此路不通！return！if target - candidates[i] < 0:return# 否则，将当前数值candidates[i]添加到path，记录正在尝试的组合情况path.append(candidates[i])# 添加后，相当于走到了下一个岔路口# 此时调用递归继续向下一层搜索！# path和result保持不变# 关键点在于，更新目标值为target-candidates[i]，表示剩余还需要凑的目标值# 本题更关键的！！！更新begin为i，# 因为candidates[i]可以被重复选择！！！所以暂时不要跳到下一个i + 1！！！self.__DFS(candidates, target - candidates[i], i, path, result)# 当下一层递归返回后，说明当前节点下的所有（可重复选）# 可能情况都已经探索完成# 将path的最后一个元素弹出，恢复到添加该元素之前的状态，# 以便尝试下一个数字作为组合的一部分# 继续生成其他可能的满足条件的数字组合path.pop()

这样修改后，__DFS 作为 Solution 类的一个正常方法，可以在 combinationSum 方法中正确被调用，代码应该能按照预期执行回溯算法来解决组合总和问题。

如果不将 __DFS 方法设置为与 combinationSum 平级（即作为 Solution 类的直接方法），而是想在 combinationSum 方法内部定义并使用类似功能的内部函数来实现回溯逻辑，也是可以的，但需要做一些调整，主要是利用闭包的特性来实现。以下是一种修改后的示例代码：

from typing import Listclass Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:"""主函数，用于调用内部函数实现回溯来解决组合问题，并返回最终结果:param candidates: 无重复元素的整数数组，从中选取数字组成满足条件target的组合:param target: 目标整数，要使得选取的数字组合的加和达到的值:return: 满足条件的所有不同组合的列表，每个组合都是一个整数列表"""# 特解：candidates空集：if len(candidates) == 0:return []# 对候选数组candidates进行预先排序，方便后续剪枝操作candidates.sort()# 准备回溯函数的参数path = []    # 记录当前正在生成的一种数字组合情况，初始是空列表result = []  # 存储最终所有满足条件的数字组合，初始是空列表# 定义内部函数，利用闭包访问外部函数的变量def inner_DFS(begin):nonlocal path, result, candidates, target# 先对path(上次递归得到的一条路)进行拷贝，# 避免后续操作中直接修改传入的path对象# （因为python中列表是可变对象，传参时可能出现意外修改情况）path = path.copy()# 设置递归出口：当目标值target==0# 说明当前path中的数字组合已经满足和为目标值的条件# 找到了一种满足条件的组合if target == 0:result.append(path)return# 遍历从begin位置开始的candidates中的元素# 逐个尝试作为组合的一部分for i in range(begin, len(candidates)):# 剪枝：如果当前值特别大，走到这个值的时候，直接超过了target# 即，target - candidates[i] < 0# 此路不通！return！if target - candidates[i] < 0:return# 否则，将当前数值candidates[i]添加到path，记录正在尝试的组合情况path.append(candidates[i])# 添加后，相当于走到了下一个岔路口# 此时调用内部函数自身进行递归，继续向下一层搜索！# 注意这里调用的是内部函数inner_DFS，不是之前的平级方法__DFSinner_DFS(i)# 当下一层递归返回后，说明当前节点下的所有（可重复选）# 可能情况都已经探索完成# 将path的最后一个元素弹出，恢复到添加该元素之前的状态，# 以便尝试下一个数字作为组合的一部分# 继续生成其他可能的满足条件的数字组合path.pop()# 调用内部函数开始回溯过程，初始begin为0inner_DFS(0)return result
——————————————————————————
超时！

在上述代码中：

• 我们在 combinationSum 方法内部定义了一个名为 inner_DFS 的内部函数，它通过 nonlocal 关键字声明了对外部函数（combinationSum）中的一些变量（path、result、candidates、target）的引用，这样就可以在内部函数中访问和修改这些外部变量，实现类似之前 __DFS 方法的功能。
• 在 combinationSum 方法中，通过调用 inner_DFS(0) 来启动回溯过程，就像之前调用 __DFS 方法一样。

这种方式利用了闭包的特性，使得在方法内部定义的函数也能够访问和操作外部函数的相关变量，从而实现回溯算法来解决组合总和问题，但整体代码结构相对来说可能没有将 __DFS 作为平级方法那么清晰直观，所以在实际应用中，更常见的还是将相关的辅助方法定义为类的直接方法（平级），以便于代码的理解和维护。