[39][中等][回溯] 组合总和

题目描述

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。

• 解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

输入：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, 2, 3]和[3, 2, 2]属于同一个结果, 因此我们可以限制下一层搜索的起点. [2, 2, 3]是先搜完2再搜3得到的结果, [3, 2, 2]则相反. 由于原数组中的元素不重复, 因此我们可以规定, 每一层搜索从指定位置开始, 包括指定位置, 只能向后不能向前搜索. 例如对于数组[2,3,6,7], 当我们在某层第一个搜索的数字是3时, 下一层就只能从3开始(数字可以被无限制重复选取), 但不能再搜索2了.

这样就能避免重复结果的出现. 对应的代码为:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []

        def dfs(path, tar, start):
            if tar == 0:
                results.append(path[:])
                return
            if tar < 0:
                return

            for i, num in enumerate(candidates[start:]):
                path.append(num)
                dfs(path, tar - num, start + i)
                path.pop()

        dfs([], target, 0)
        return results