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.

state:dp[i][j][t] 前i个数取出j个和为t 所以j必须要小于i

function: dp[i][j][t] = dp[i-1][j][t] 如果t >= A中第i个数 dp[i][j][t] += dp[i-1][j-1][t-A[i-1]]

（1）我们可以把当前A[i - 1]这个值包括进来，所以需要加上D[i - 1][j - 1][t - A[i - 1]]（前提是t - A[i - 1]要大于0）

（2）我们可以不选择A[i - 1]这个值，这种情况就是D[i - 1][j][t]，也就是说直接在前i-1个值里选择一些值加到target.

initial: dp[i][0][0] = 0

return: dp[i][k][target]

public class Solution {

    public int kSum(int A[], int k, int target) {
        int m = A.length;
        int[][][] dp = new int[A.length + 1][k+1][target+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= k && j <= i; j++) {// j必须要比i小
                for (int n = 1; n <= target; n++) {
                    dp[i][j][n] = dp[i-1][j][n];
                    if (n >= A[i-1]) {// 是大于等于不是大于
                        dp[i][j][n] += dp[i-1][j-1][n- A[i-1]];
                    }
                    
                }
            }
        }
        return dp[m][k][target];
        
    }
}