Description

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 are2solutions:[1,4]and[2,3]. Return2.

Solution

三维动态规划。dp[i][j][t]表示前i个数中取j个数相加为t的组合个数，取决于包括第i个数和不包括第i个数两种情况。
状态方程 dp[i][j][t] = dp[i-1][j][t] + dp[i-1][j-1][t-A[i]](t >= A[i])
初始状态dp[i][0][0] = 1, 0 <= i <= A.length （凡是求count的初始状态都是1）

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    public int kSum(int A[], int k, int target) {
        // write your code here
        int[][][] dp = new int[A.length+1][k+1][target+1];
        for (int i = 0; i <= A.length; i++) {
            dp[i][0][0] = 1;
        }

        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= k; j++) {
                for (int t = 1; t <= target; t++) {
                    dp[i][j][t] = dp[i-1][j][t];
                    if (t >= A[i-1]) {
                        dp[i][j][t] += dp[i-1][j-1][t-A[i-1]];
                    }
                }
            }
        }

        return dp[A.length][k][target];
    }
}