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 dfs search algorithm. As we can use the elements of candidates repetitively, the children node of each node would be all element of the candidates. Applying the dfs by 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

Leetcode No.55 Jump Game

Leetcode No.22 Generate Parentheses