Leetcode No.39 Combination Sum
2022/11/07The dfs solution to leetcode no. 39. Medium level.
algorithm
dfs
Question
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
python
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]Solution
第一反应是使用 dfs 搜索算法。因为可以重复使用元素，所以每个节点的子节点是 candidates 中的各个元素。
使用回溯法编写脚本如下：
The first thought is using
dfssearch algorithm. As we can use the elements ofcandidatesrepetitively, the children node of each node would be all element of thecandidates. Applying thedfsby recursively traversing.
python
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
ans = []
def dfs(candidates, t, l):
for c in candidates:
if c == t:
ans.append(l+[c])
elif c > t:
continue
else:
dfs(candidates, t-c, l+[c])
dfs(candidates, target, [])
return ans此时的结果为:
print(combinationSum([2, 3, 6, 7], 7))
[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]并发现有重复的答案，通过观察发现有以下规律：
- 向下搜索时，总是从左端开始，也就是小的数字开始
- 重复的现象出现于：先到达值较大的节点，然后搜索值小的节点。然而这种情况必然导致重复，因为我们每次都是从值小的节点开始搜索的。
因此，为了去重我们需要这样做：每次到达某节点时，若该节点的值比 遍历过的最大值 小， 那么我们有理由认为这将导致重复的结果，因此只需添加一个判断即可：
python
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
ans = []
def dfs(candidates, t, l):
for c in candidates:
if len(l) and c < max(l):
continue
if c == t:
ans.append(l+[c])
elif c > t:
continue
else:
dfs(candidates, t-c, l+[c])
dfs(candidates, target, [])
return ans