Given n unique integers, number k (1<=k<=n) and target.
Find all possible k integers where their sum is target.
Example
Given [1,2,3,4], k = 2, target = 5. Return:
[
[1,4],
[2,3]
]
Solution
sum or total question , the check point is target - current value == 0 and dont' do currentvalue == target.
put the if inside of for in range , it will give the good performance.
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
"""
def kSumII(self, nums, k, target):
# write your code here
result = []
self.DFS(result, nums, k, target, [], 0)
return result
def DFS(self, result, nums, k, target, current, pos):
if len(current) == k and target == 0:
result.append(list(current))
for i in range(pos, len(nums)):
if target - nums[i] >= 0:
current.append(nums[i])
self.DFS(result, nums, k, target - nums[i], current, i + 1)
del current[-1]