Leetcode 39.组合总和

1.题目描述

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

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

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

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都 互不相同
• 1 <= target <= 500

2.思路分析

举个栗子:andidates = [2,5,3], target = 4,搜索树结果抽象如下:

本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

回溯三部曲

• 确定回溯函数的参数以及返回值

  # 存放结果集
  result = []
  # 存放符合条件的结果(叶子结点的结果)
  path = []
  def backtrack(candidates: List[int], target: int, path_sum: int, startIndex: int) -> None:
  1
  2
  3
  4
  5

• 确定终止条件

  从上图的树形结构中可以看出:sum>=target时,递归终止,sum==target时收集结果

     # Base Case
          if sum_ == target:
              self.paths.append(path[:]) # 因为shallow copy，不能直接传入path
              return
          if sum_ > target:
              return 
  1
  2
  3
  4
  5
  6

• 确定单层搜索逻辑

  • 单层for循环依然是从startIndex开始，搜索candidates集合。

  # 单层递归逻辑 
          for i in range(start_index, len(candidates)):
              sum_ += candidates[i]
              self.path.append(candidates[i])
              self.backtracking(candidates, target, sum_, i)  # 因为无限制重复选取，所以不是i+1
              sum_ -= candidates[i]   # 回溯
              self.path.pop()        # 回溯
  1
  2
  3
  4
  5
  6
  7

3.代码实现

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        '''
        因为本题没有组合数量限制，所以只要元素总和大于target就算结束
        '''
        self.path.clear()
        self.paths.clear()
        self.backtracking(candidates, target, 0, 0)
        return self.paths

    def backtracking(self, candidates: List[int], target: int, path_sum: int, start_index: int) -> None:
        # Base Case
        if path_sum == target:
            self.paths.append(self.path[:]) # 因为是shallow copy，所以不能直接传入self.path
            return
        if path_sum > target:
            return 
        
        # 单层递归逻辑 
        for i in range(start_index, len(candidates)):
            path_sum += candidates[i]
            self.path.append(candidates[i])
            self.backtracking(candidates, target, path_sum, i)  # 因为无限制重复选取，所以不是i+1
            path_sum -= candidates[i]   # 回溯
            self.path.pop()        # 回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

4.剪枝优化

如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        '''
        因为本题没有组合数量限制，所以只要元素总和大于target就算结束
        '''
        self.path.clear()
        self.paths.clear()

        # 为了剪枝需要提前进行排序
        candidates.sort()
        self.backtracking(candidates, target, 0, 0)
        return self.paths

    def backtracking(self, candidates: List[int], target: int, path_sum: int, start_index: int) -> None:
        # Base Case
        if path_sum == target:
            self.paths.append(self.path[:]) # 因为是shallow copy，所以不能直接传入self.path
            return
        # 单层递归逻辑 
        # 如果本层 sum + condidates[i] > target，就提前结束遍历，剪枝
        for i in range(start_index, len(candidates)):
            if path_sum + candidates[i] > target: 
                return 
            path_sum += candidates[i]
            self.path.append(candidates[i])
            self.backtracking(candidates, target, path_sum, i)  # 因为无限制重复选取，所以不是i-1
            path_sum -= candidates[i]   # 回溯
            self.path.pop()        # 回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32