Lintcode: 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.

当然这道题可以用Recursion的方法，找出所有满足条件的组合，然后求结果arraylist的size，不过对于只需要求多少个可行解的这道题，找出所有满足条件的组合显得过于奢侈了

如果只需要求一个可行解个数，一个3维DP就好了

没有管优化：要注意base case的选取。

我第一次做的时候只定义了 res[0][0][0] = 1, 其实res[i][0][0] = 1, 漏了这些case，所以当时老是过不了

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[][][] res = new int[A.length+1][k+1][target+1];
        for (int i=0; i<=A.length; i++) {
            res[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++) {
                    if (j > i) res[i][j][t] = 0;
                    else res[i][j][t] = res[i-1][j][t];
                    if (t >= A[i-1])
                        res[i][j][t] += res[i-1][j-1][t-A[i-1]];
                    
                }
            }
        }
        return res[A.length][k][target];
    }
}