k Sum
Written on October 21, 2015
Tweet
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?
public class Solution {
/**
* @param A: an integer array.
* @param k: a positive integer (k <= length(A))
* @param target: a integer
* @return an integer
*/
public int count = 0;
public int kSum(int A[], int k, int target) {
// write your code here
if (A == null || A.length == 0) return 0;
int[][][] dp = new int[A.length + 1][k + 1][target+1];
//dp[i][j][k] from i numbers pick j numbers sum to target
for (int i = 0; i <= A.length; i++) {
dp[i][0][0] = 1;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k; j++) {
for (int l = 1; l <= target; l++) {
dp[i][j][l] = dp[i-1][j][l];
if (A[i-1] <= l) {
dp[i][j][l] += dp[i-1][j-1][l-A[i-1]];
}
}
}
}
return dp[A.length][k][target];
}
}