LeetCode Combination Sum

LeetCode解題之Combination Sum

原題

在一個集合（沒有重復數字）中找到和為特定值的所有組合。

注意點：

例子：

輸入: candidates = [2, 3, 6, 7], target = 7
輸出: [[2, 2, 3], [7]]

解題思路

采用回溯法。由於組合中的數字要按序排列，我們先將集合中的數排序。依次把數字放入組合中，因為所有數都是正數，如果當前和已經超出目標值，則放棄；如果和為目標值，則加入結果集；如果和小於目標值，則繼續增加元素。由於結果集中不允許出現重復的組合，所以增加元素時只增加當前元素及之後的元素。

AC源碼

class Solution(object):
    def combinationSum(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:
            for i, v in enumerate(candidates):
                self.combination(candidates[i:], target, current + [v], result)


if __name__ == "__main__":
    assert Solution().combinationSum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]

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