# K Sum

Lintcode Online Judge

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];
}```
Share