k Sum II

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]