LeetCode Combination Sum II

LeetCode解題之Combination Sum II

原題

在一個數組（存在重復值）中尋找和為特定值的組合。

注意點：

例子：

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

解題思路

這道題和 Combination Sum 極其相似，主要的區別是Combination Sum中的元素是沒有重復的，且每個元素可以使用無限次；而這題中的元素是有重復的，每個元素最多只能使用一次。最開始的想法是加下一個元素時不要考慮當前元素，且把結果用集合存儲以防止重復的組合出現，但結果超時了。改用手動把所有與當前元素相等的元素都去掉即可。

AC源碼

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)
        return result

    def combination(self, candidates, target, current, result):
        s = sum(current) if current else 0
        if s > target:
            return
        elif s == target:
            result.append(current)
            return
        else:
            i = 0
            while i < len(candidates):
                self.combination(candidates[i + 1:], target, current + [candidates[i]], result)
                # ignore repeating elements
                while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
                    i += 1
                i += 1


if __name__ == "__main__":
    assert Solution().combinationSum2([10, 1, 2, 7, 6, 1, 5], 8) == [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

歡迎查看我的Github來獲得相關源碼。