k-sum

gistfile1.txt

public class Solution {
    /*
     * @param A: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integer
     */
    public int kSum(int[] A, int k, int target) {
        int n = A.length;
        int[][][] dp = new int[n+1][k+1][target+1];
        for (int i=0; i <=n; i++) {
            dp[i][0][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j=1; j <= k && j <= i; j++) {
                for(int s = 1; s <= target; s++) {
                    //dp[i-1][j][s] = 没选i直接等于s
                    dp[i][j][s] = dp[i-1][j][s];
                    if (s >= A[i-1]) {
                        //选 i
                        dp[i][j][s] += dp[i-1][j-1][s-A[i-1]]; // A index is 0 so i-1
                    }
                }
            }    
        }
        //dp[i][j][s] = 前i个里面有多少种方法选j ( j <= k )和为s ＝ 多少
        //dp[i-1][j][s] = 没选i直接等于s
        return dp[n][k][target];
    }
}