[LintCode] #89 K Sum

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    
    // state: f[i][j][t] - for the first i elements in A, pick j elements, how many solutions are there to get sum = t
    // function: f[i][j][t] = f[i - 1][j - 1][t - A[i]] + f[i - 1][j][t]
    // initialize: f[0][0][0] = 1;
    // result: f[A.length][k][target]
    public int kSum(int A[], int k, int target) {
        // write your code here
        if (A == null || A.length == 0 || k == 0) {
            return 0;
        }
        int[][][] f = new int[A.length + 1][k + 1][target + 1];
        
        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= k; j++) {
                for (int t = 0; t <= target; t++) {
                    if (j == 0 && t == 0) {
                        f[i][j][t] = 1;
                        break;
                    } else if (i == 0) {
                        f[i][j][t] = 0;
                        break;
                    } else if (j != 0 && t - A[i - 1] >= 0) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                }
            }
        }
        
        return f[A.length][k][target];
    }
}