原題
給定n個(gè)不同的正整數(shù)，整數(shù)k（1<= k <= n）以及一個(gè)目標(biāo)數(shù)字鹅士。
在這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])
