k Sum

k Sum

19%

Accepted

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?

Have you met this question in a real interview? 

Yes

Example

Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

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 kSum(int A[], int k, int target) {
        // write your code here
        int[][] record = new int[k+1][target+1];
        record[0][0] = 1;
        for(int i = 0; i < A.length; i++){
            for(int j = target; j >= 1; j--){
                for(int l = 1; l <=k ; l++){
                    if(j >= A[i]){
                        record[l][j] += record[l-1][j - A[i]];
                    }
                }
            }
        }
        return record[k][target];
    }
}