K Sum

Lintcode Online Judge

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.

Solution: DP

state:  f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x][0][0] = 1

O(n*k*t) time O(n*k*t) space

public int kSum(int A[], int k, int target) {
    if (A == null) {
        return 0;
    }
    //kSum[i][j][t]:find j integers from first i integers in the array
    //how many solutions there are to sum up to t
    int[][][] kSum = new int[A.length + 1][k + 1][target + 1];
    for (int i = 0; i <= A.length; i++) {
        kSum[i][0][0] = 1; //select nothing which is also a solution
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= k; j++) {
            for (int t = 1; t <= target; t++) {
                kSum[i][j][t] = kSum[i - 1][j][t];
                if (t >= A[i - 1]) {
                    kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]];
                }
            }
        }
    }
    return kSum[A.length][k][target];
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *