leetcode刷题-40组合总和2

题目

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

candidates 中的每个数字在每个组合中只能使用一次。

思路

此题思路与39题类似，利用回溯的方式，但是难点在于不能重复利用。

避免重复要让同一层级不出现相同的元素，却允许了不同层级之间的重复相同元素：

1
/ \
2 2 这种情况不会发生
/ \
5 5

1
/
2 这种情况确是允许的
/
2

因此在剪枝时，需要将重复的元素删除。

算法：

1.对candidates进行排序

2.回溯函数combination：索引i，当前数组tmp，下一目标target：

　　2.1 当target == 0时，满足条件，tmp添加进入result

　　2.2 剪枝当索引等于candidates长度的时候，已经结束，return；当target < candidates[i]的时候，后续也不存在满足的结果，因此剪枝，return。

　　2.3 调用后续元素(不允许重复)，在j遍历区间[i,n)中：

　　　　2.3.1 剪枝当j>idx 且candidates[j]==candidates[j-1]时，会调用重复的元素，将其删除

　　　　2.3.2 调用下一元素

实现

class Solution:

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        if(not candidates):

            return []

        n=len(candidates)

        result=[]

        candidates.sort()

        def combination(idx, tmp, target):

            print(idx, tmp, target)

            if target == 0 :

                result.append(tmp)

                return

            if idx == n or target < candidates[idx]:

                return

            for j in range(idx, n):

                if j>idx and candidates[j]==candidates[j-1]:

                    continue

                combination(j+1, tmp+[candidates[j]],target-candidates[j])

        combination(0,[],target)

        return result

巴特西

leetcode刷题-40组合总和2

题目

思路

实现

最新文章

热门文章