k Sum

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.

------------------------ thinking -----------------------
there are two situation for each integer, either count it or not in the dp
http://tech-wonderland.net/blog/summary-of-ksum-problems.html
https://richdalgo.wordpress.com/2015/01/31/lintcode-k-sum/
----------------------- codes ----------------------------
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 dp[A.size()][k+1][target+1];
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j <= k; j++) {
                for (int val = 0; val <= target; val++) {
                    dp[i][j][val] = 0;
                }
            }
        }
        for (int i = 0; i < A.size(); i++) {
            for (int j = 1; j <= k; j++) {
                for (int val = 1; val <= target; val++) {
                    if (j == 1 && A[i] == val) {
                        dp[i][1][val] = 1;
                    } else if (i > 0) {
                        if (A[i] <= val) {
                            dp[i][j][val] += dp[i-1][j-1][val-A[i]];
                        }
                        dp[i][j][val] += dp[i-1][j][val];
                    }
                }
            }
        }
        return dp[A.size() - 1][k][target];
    }
};