Leetcode 40:组合总和 II(最详细的解法!!!)
in leetcode with 0 comment

Leetcode 40:组合总和 II(最详细的解法!!!)

in leetcode with 0 comment

给定一个数组 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]
]

解题思路

这个问题是之前这个问题( Leetcode 39:组合总和(最详细的解法!!!))的延伸。很多人上来就修改

self._combinationSum2(nums, target-nums[i], i + 1, path+[nums[i]], res)# i -> i + 1

这样子的修改会出现这样的问题。对于1,71,2,5结果中会出现两次,因为我们有两个1。那要怎么做呢?最简单的做法就是增加一步检查,判断要加入的path是不是在result中。

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = list()
        candidates.sort()
        self._combinationSum2(candidates, target, 0, list(), result)
        return result
        
    def _combinationSum2(self, nums, target, index, path, res):
        if target == 0 and path not in res:# add path in res
            res.append(path)
            return 

        if path and target < path[-1]:
            return
       
        for i in range(index, len(nums)):
            self._combinationSum2(nums, target-nums[i], i + 1, path+[nums[i]], res)

但是这样子做很明显不是最优的解法,我们能不能优化它?我们只要在循环中添加一步控制即可。

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = list()
        candidates.sort()
        self._combinationSum2(candidates, target, 0, list(), result)
        return result
        
    def _combinationSum2(self, nums, target, index, path, res):
        if target == 0:
            res.append(path)
            return 

        if path and target < path[-1]:
            return
       
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i - 1]: # add
                continue
            self._combinationSum2(nums, target-nums[i], i + 1, path+[nums[i]], res)

在递归前判断nums[i]nums[i - 1]是不是相等,如果是的话,表示此时添加了重复元素,跳过即可;否则的话,我们进入下一步递归。

另外,我们也可以这么考虑,对于k个重复元素,我们考虑添加0~k次重复元素的情况,所以有k次递归调用的过程。那么代码可以写成:

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = list()
        candidates.sort()
        self._combinationSum2(candidates, target, 0, list(), result)
        return result
        
    def _combinationSum2(self, nums, target, index, path, res):
        if target == 0:
            res.append(path[::])
            return 

        if index == len(nums) or (path and target < path[-1]):
            return

        k = index
        while k < len(nums) and nums[k] == nums[index]:
            k += 1
        
        self._combinationSum2(nums, target, k, path, res) #不添加相同元素
        for i in range(index, k): #添加1~k-index个相同元素
            path.append(nums[i])
            self._combinationSum2(nums, target - nums[index]*(i-index + 1), k, path, res)
        for i in range(index, k): #弹出末尾所有相同元素
            path.pop()

和问题Leetcode 90:子集 II(最详细的解法!!!)一模一样,大家可以比较这练习。

同样的,对于递归可以解决的问题,我们都应该思考是不是可以通过迭代解决。这就很容易了,我们只要在之前问题的迭代基础上修改一下即可。

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        result = list()
        stack = [(0, list(), target)]
        cand_len = len(candidates)

        while stack:
            index, path, remain = stack.pop()
            for i in range(index, cand_len):
                if i > index and candidates[i] == candidates[i-1]:# add
                    continue

                if path and remain < path[-1]:
                    break

                if candidates[i] == remain: 
                    result.append(path + [candidates[i]])
               
                stack += [(i + 1, path + [candidates[i]],  remain - candidates[i])]#add

        return result

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses