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