K sum

Given n distinct positive integers, integer k (k <= n) and a numbertarget.

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.

After we have 2 sum, 3 sum and 4 sum, finally we are embracing k sum. It's easy to think of using backtracking approach... if the question is to find all solutions. However, in the problem, we are asked to give the number of possible solutions. Of course you can still use backtracking, yet the complexity will be way to high for solving the problem.

Usually when we see find the number of solutions, we can guess it may relate to DP. So yes, this problem also uses DP approach. Here we have a 3-D matrix, the first dimension represents array length (number of candidate numbers), the second one represents how many numbers allowed to find the solution, and the last one is the target we want to find.

So initial condition:

matrix[i][0][0] = 1

This means we want to find 0 numbers in i numbers with sum 0.

The recursive formula:

matrix[i][j][t] = matrix[i - 1][j][t] + (t >= A[i - 1]) ? matrix[i - 1][j - 1][t - A[i - 1]] : 0

The first part means the number of solutions in matrix[i][j][t] is the same as the number of solutions of finding j numbers in i - 1 numbers with sum t. The second part indicates if current A[i -1] is smaller than t, the number of solutions should also add finding j - 1 numbers in i - 1 numbers with target t - A[i - 1], because adding A[i] will get us target t.

public int kSum(int A[], int k, int target) {
        
        int[][][] matrix = new int[A.length + 1][k + 1][target + 1];
        
        for (int i = 0; i <= A.length; i++) {
            matrix[i][0][0] = 1;
        }
        
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    matrix[i][j][t] = matrix[i - 1][j][t] + (t >= A[i - 1] ? matrix[i - 1][j - 1][t - A[i - 1]] : 0);
                }
            }
        }
        return matrix[A.length][k][target];
}