Givenn_distinct positive integers, integer_k(k<=n) and a numbertarget.

Find_k_numbers where sum is target. Calculate how many solutions there are?

Have you met this question in a real interview?

Yes

Example

Given[1,2,3,4], k =2, target =5.

There are2solutions:[1,4]and[2,3].

Return2.

背包动态规划

如果去除了条件k个元素，则此题转化为背包问题

所以加了一个元素，则可以把该元素加入到状态中

f[i][j][k] 为在前i个元素中选j个有多少种方法拼出k值

f[i][j][k] = f[i - 1][k - 1][j - A[i - 1] + f[i - 1][k][j]

f[0][0][0] = 1

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) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }

        int[][][] f = new int[A.length + 1][k + 1][target + 1];
        f[0][0][0] = 1;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 0; j <= k; j++) {
                for (int t = 0; t <= target; t++) {
                    f[i][j][t] = f[i - 1][j][t];

                    if (t >= A[i - 1] && j > 0) {
                        f[i][j][t] += f[i - 1][j - 1][t - A[i - 1]];   
                    }
                }
            }
        }
        return f[A.length][k][target];
    }
}