leetcode第40题：组合总和II

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

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

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

所求解集为:

[

  [1, 7],

  [1, 2, 5],

  [2, 6],

  [1, 1, 6]

]

示例 2：输入: candidates = [2,5,2,1,2], target = 5,所求解集为:

[

  [1,2,2],

  [5]

]

解题思路类似上一题，
不同之处是这道题不允许重复使用candidates中的元素。
我们可以直接在上一道题目的代码上修改，递归的时候将 idx 加 1（需判断是否超出candidates的范围），另外由于题目输入的candidates可能包含相同的元素，所以我们需要对得到的答案进行去重处理。

代码如下：

class Solution:

    def Slover(self, candidates, target, res, path, idx):

        for i in range(idx, len(candidates)):

            new_target = target - candidates[i]

            if new_target < 0:

                return

            else:

                if new_target == 0:

                    res.append(path + [candidates[i]])

                else:

                    idx = idx + 1

                    if idx < len(candidates):

                        self.Slover(candidates, new_target, res, path + [candidates[i]], idx)

                    else:

                        return

    def combinationSum2(self, candidates, target):

        """

        :type candidates: List[int]

        :type target: int

        :rtype: List[List[int]]

        """

        res = []

        path = []

        idx = 0

        candidates = sorted(candidates)

        self.Slover(candidates, target, res, path, idx)

        ud_res = []

        for r in res:

            if r not in ud_res:

                ud_res.append(r)

        return ud_res

巴特西

leetcode第40题：组合总和II

最新文章

热门文章