K Sum II

Question

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, [1,4] and `[2,3]`` are possible solutions.

Thoughts

与subsets类似,改掉判定加入result list的条件

Solution

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, A, k, target):
        # write your code here
        self.A = A
        self.A.sort()
        self.resultList = []
        self.subsetHelper([], 0, k, target)
        return self.resultList

    def subsetHelper(self, curList, pos, k, target):
        if len(curList) == k and sum(curList) == target:
            newList = list(curList)
            self.resultList.append(newList)
        if len(curList) > k:
            return

        for i in range(pos, len(self.A)):
            curList.append(self.A[i])
            self.subsetHelper(curList, i + 1, k, target)
            curList.pop()