Lintcode90. k Sum II

class Solution:
    """
    @param: A: an integer array
    @param: k: a postive integer <= length(A)
    @param: targer: an integer
    @return: A list of lists of integer
    """
    # A: the input
    # k: currently remained intergers
    # target: target
    # start: start position in A
    # curr: curr solution
    # sums: sum of curr solution
    def DFS (self, A, k , target, start, result , curr, sums):
        if k == 1:
            i = start
            while i < len(A):
                # print i, curr, result, sums, A[i]
                if sums + A[i] == target:
                    result.append (curr + [A[i]])
                if sums + A[i] > target:
                    i = len(A)
                i += 1
        else:
            i = start
            while i < len(A):
                if sums + A[i] < target:
                    self.DFS (A, k - 1, target, i + 1, result, curr + [A[i]], sums + A[i])
                    i += 1
                else:
                    i = len(A)
                    
                    
    def kSumII(self, A, k, target):
        # write your code here
        if len(A) == 0 or k == 0 or sum(A) < target:
            return []
        A.sort()
        result = []
        curr = []
        sums = 0
        self.DFS (A, k, target, 0, result, curr, sums)
        return result