Givenn_distinct positive integers, integer_k(k<=n) and a numbertarget.

Find_k_numbers where sum is target. Calculate how many solutions there are?

Have you met this question in a real interview?

Yes

Example

Given[1,2,3,4], k =2, target =5.

There are2solutions:[1,4]and[2,3].

Return2.

class Solution {

public:

/**

 * @param A: an integer array.

 * @param k: a positive integer (k <= length(A))

 * @param target: a integer

 * @return an integer

 */

int kSum(vector<int> A, int k, int target) {

    // wirte your code here

    int n = A.size();

    vector<vector<int>> f(k + 1, vector<int>(target + 1, 0));

    f[0][0] = 1;



    for (int i = 1; i <= n; ++i) {

        for (int j = min(k, i); j >= 1; --j) {

            for (int m = target; m >= A[i - 1]; --m) {

                f[j][m] += f[j - 1][m - A[i - 1]];

            }

        }

    }

    return f[k][target];

}
};