[Leetcode][python]Combination Sum II/组合总和 II

蛮三刀酱

发布于 2019-03-26 16:24:48

5390

发布于 2019-03-26 16:24:48

文章被收录于专栏：蛮三刀的后端开发专栏蛮三刀的后端开发专栏

题目大意

在一个数组（存在重复值）中寻找和为特定值的组合。+

注意点：

所有数字都是正数组合中的数字要按照从小到大的顺序原数组中的数字只可以出现一次结果集中不能够有重复的组合

解题思路

这道题和 Combination Sum 极其相似，主要的区别是Combination Sum中的元素是没有重复的，且每个元素可以使用无限次；而这题中的元素是有重复的，每个元素最多只能使用一次。

代码

更改上一题代码： 1. 将candidates[i:]变为candidates[i+1:] 2. 再加入flag让后面不必要的累加提前结束（上一题也适用，后来想到的） 3. 最后结果有重复，去重

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not candidates:
            return []
        candidates.sort()
        result = []
        self.combination(candidates, target, [], result)
        new_result = []
        for res in result:
            if res not in new_result:
                new_result.append(res)
        # print new_result
        return new_result

    def combination(self, candidates, target, current, result):
        # print 'candidates', candidates
        if current:
            # print 'current:', current
            s = sum(current)
        else: 
            s = 0
        if s > target:
            return 1 # 从这里结束匹配不了的循环
        elif s == target:
            # print 'result:', current
            result.append(current)
            return 1
        else:
            for i, v in enumerate(candidates):
                # print i, v
                flag = self.combination(candidates[i+1:], target, current + [v], result)
                if flag == 1:
                    break

总结

事后在想能不能直接用set存储，这样就不用去重了，但是应该不行，因为set的key不能使可变对象，而慢慢累加的list是不能用tuple来代替存储的。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年09月21日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

存储

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

存储

登录后参与评论

0 条评论

热度