LintCode 90 [k Sum II]

原题

给定n个不同的正整数，整数k（1<= k <= n）以及一个目标数字。　　　　
在这n个数里面找出K个数，使得这K个数的和等于目标数字，你需要找出所有满足要求的方案。

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

解题思路

• 由于k Sum是求个数，所以考虑动态规划，直接DFS会超时。而k Sum II 是求所有具体的解，所以直接DFS.
• 思路跟 subsets 类似，可以想象成求一些特殊的subsets，加入result时，要符合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])