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`

.

Solution: DP

state: f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x][0][0] = 1

O(n*k*t) time O(n*k*t) space

public int kSum(int A[], int k, int target) { if (A == null) { return 0; } //kSum[i][j][t]:find j integers from first i integers in the array //how many solutions there are to sum up to t int[][][] kSum = new int[A.length + 1][k + 1][target + 1]; for (int i = 0; i <= A.length; i++) { kSum[i][0][0] = 1; //select nothing which is also a solution } for (int i = 1; i <= A.length; i++) { for (int j = 1; j <= k; j++) { for (int t = 1; t <= target; t++) { kSum[i][j][t] = kSum[i - 1][j][t]; if (t >= A[i - 1]) { kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]]; } } } } return kSum[A.length][k][target]; }