[LintCode] k Sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

This problem is similar with backpack, but it has a constraint of k elements.

class Solution {
public:
    int kSum(vector<int> A, int k, int target) 
    {
        vector<vector<int>> rec(target+1, vector<int>(k, 0));
        for(int i=0;i<A.size();i++)
        {
            for(int j=target; j>=A[i]; j--)
            {
                if(A[i] == j) rec[j][0]++;
                for(int v = 0; v < min(k-1,i); v++)
                {
                    rec[j][v+1] += rec[j-A[i]][v];
                }
            }
        }
        return rec[target][k-1];
    }
};