LintCode: K Sum

The problem:
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.

http://www.mitbbs.com/article_t/JobHunting/32839945.html

 

Solution 1: Recursion
class Solution {
public:
   
    void helper(vector<int> A,int k, int start,int target, int & ans) {
        if (k < 0 || target < 0) return;
       
        if (k == 0 && target == 0) {
            ans++;
            return;
        }
       
        for(int i = start; i <= A.size()-k; i++)
            helper(A, k-1, i+1, target - A[i], ans);
    }
   
    int solutionKSum(vector<int> A,int k,int target) {
        int ans = 0;
        helper(A, k, 0, target, ans);
        return ans;
    }
};

/*
DP
map[I][j][t] denotes the number of ways to select, from first i elements, j elements whose sum equals to target
*/
class Solution2 {
public:
    int solutionKSum(vector<int> A,int k,int target) {
        int n = A.size();
       
        vector<vector<vector<int>>> map(n+1, vector<vector<int>>(k+1, vector<int>(target+1, 0)));
       
        for(int i = 1; i <=n; i++) {
            if (A[i-1] <= target)
            { 
                for(int j = i; j <=n; j++)
                   map[j][1][A[i-1]] = 1;
            }
        }
       
        for(int i = 1; i <= n; i++)
          for(int j = min(i, k); j > 1; j--)
              for(int p = 1; p <= target; p++)
              {
                  map[i][j][p] = map[i-1][j][p];
                  if (p-A[i-1] >=0)
                     map[i][j][p] += map[i-1][j-1][p-A[i-1]];
              }
         
        return map[n][k][target];
    }
};

   int kSum(vector<int> A,int k,int target) {
        int n = A.size();
        
        vector<vector<int>> map(k+1, vector<int>(target+1, 0));
        
        for(int i = 1; i <= n; i++) 
          for(int j = min(i, k); j >= 1; j--) {
               for(int t = target; t >= A[i-1]; t--) {
                   // map[j][t] denotes the total number of ways to 
                   // select j elements,
                   // from the first i elements
                   // and the j elements sums up to t
                   if (j==1) 
                       map[1][t] += A[i-1] == t ? 1 : 0;
                   else
                       map[j][t] += map[j-1][t-A[i-1]];
              } 
          }
          
        return map[k][target];
    }