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

桃扇骨 2022-06-08 09:11 191阅读 0赞

## 题目大意 ##

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

注意点：

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

## 解题思路 ##

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

## 代码 ##

更改[上一题][Link 1]代码：  
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来代替存储的。

[Link 1]: http://blog.csdn.net/qqxx6661/article/details/77998262