Lintcode 89. k Sum

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

Example 1

Input:
List = [1,2,3,4]
k = 2
target = 5
Output: 2
Explanation: 1 + 4 = 2 + 3 = 5

Example 2

Input:
List = [1,2,3,4,5]
k = 3
target = 6
Output: 1
Explanation: There is only one method. 1 + 2 + 3 = 6

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

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) {         if (A == null || A.length == 0 || k <= 0 || target <= 0) {             return 0;         }                   int[][][] dp = new int[A.length + 1][k + 1][target + 1];         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 <= Math.min(i, k); j++) {                 for (int t = 1; t <= target; t++) {                     dp[i][j][t] = dp[i - 1][j][t];                     if (t - A[i - 1] >= 0) {                         dp[i][j][t] += dp[i - 1][j - 1][t - A[i - 1]];                     }                 }             }         }                   return dp[A.length][k][target];     } }