Lintcode: 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

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

Understand the problem:
It is another back pack problem, choosing k items out of n items, where its sum equals to k. 
So we could still use back pack DP solution.

Solution:
Idea: Using back pack dp

• Definition:    dp[n + 1][k + 1][target + 1], where dp[i][j][m] means choosing j elements out of the first i elements, and its sum equals to m
• Initial state:  dp[0][0][0] = 1, dp[i][0][0] = 1, 1 <= i <= n
• Transit function:  
• dp[i][j][m] = dp[i - 1][j][m]   // no choose item i
• if (A[i - 1] <= m) dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]  // choose item i
• Final state:  dp[n][k][target];

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 32 33 34 35 36 37

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 solutionKSum(int A[],int k,int target) {         // write your code here         if ((A == null || A.length == 0) && k == 0 && target == 0) {             return 1;         }                   if (A == null || A.length == 0 || k <= 0 || target <= 0 || k > A.length) {             return 0;         }                   int[][][] dp = new int[A.length + 1][k + 1][target + 1];         dp[0][0][0] = 1;         for (int i = 1; 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 m = 1; m <= target; m++) {                     dp[i][j][m] = dp[i - 1][j][m]; // no choose item i                                           if (A[i - 1] <= m) {                         dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]; // chose item i                     }                 }             }         }         return dp[A.length][k][target];     } }