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

class Solution {
public:
    void calc(vector<vector<int> > &res, vector<int> &one, vector<int> &A,
                int s, int k, int target)
    {
        if(k == 0)
        {
            if(0 == target) res.push_back(one);
            return;
        }
        
        for(int i=s;i<A.size() && A[i] <= target;i++)
        {
            one.push_back(A[i]);
            calc(res, one, A, i+1, k-1, target-A[i]);
            one.pop_back();
        }
    }
    
    vector<vector<int> > kSumII(vector<int> A, int k, int target) {
        // write your code here
        sort(A.begin(), A.end());
        vector<vector<int> > res;
        vector<int> one;
        calc(res, one, A, 0, k, target);
        return res;
    }
};