原題

給定n個(gè)不同的正整數(shù)，整數(shù)k（1<= k <= n）以及一個(gè)目標(biāo)數(shù)字?！　　　?br> 在這n個(gè)數(shù)里面找出K個(gè)數(shù)，使得這K個(gè)數(shù)的和等于目標(biāo)數(shù)字，你需要找出所有滿足要求的方案。

樣例
給出[1,2,3,4]，k=2， target=5，返回 [[1,4], [2,3]]

解題思路

• 由于k Sum是求個(gè)數(shù)，所以考慮動(dòng)態(tài)規(guī)劃，直接DFS會(huì)超時(shí)。而k Sum II 是求所有具體的解，所以直接DFS.
• 思路跟 subsets 類似，可以想象成求一些特殊的subsets，加入result時(shí)，要符合subset的和等于target
• 本題與 Combination Sum II 也非常類似

完整代碼

class Solution:
    """
    @param A: An integer array.
    @param k: A positive integer (k <= length(A))
    @param target: Integer
    @return a list of lists of integer 
    """
    res = []
    def kSumII(self, A, k, target):
        # write your code here
        if A == None:
            return []
        self.dfs(sorted(A), k, 0, [], target)
        return self.res
        
    def dfs(self, nums, k, index, path, target):
        if target == 0 and k == 0:
            self.res.append(path[:])
            return None
        if len(nums) == index or k < 0 or target < 0:
            return None
        for i in range(index, len(nums)):
            self.dfs(nums, k - 1, i+1, path + [nums[i]], target - nums[i])