k Sum 89

Question

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

用三维动态规划。

ksum[i][j][l]表示前j个元素里面取l个元素之和为i。

初始化：ksum[0][j][0] =1(j:0~n)，即前j个元素里面取0个元素使其和为0的方法只有1种，那就是什么都不取

状态函数：

ksum[i][j][l]=ksum[i][j-1][l]+ksum[i-A[i-1]][j-1][l-1]

即前j个元素里面取l个元素之和为i由两种情况组成：第一种情况为不包含第i个元素，即前j－1个元素里取l个元素使其和为i，第二种情况为包含第i个元素，即前j－1个元素里取l－1个元素使其和为i-A[i-1]（前提是i-A[i-1]>=0）。

代码如下：

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
        if(A == null || A.length == 0){
            return 0;
        }

        int n = A.length;
        int[][][] ksum = new int[target + 1][n + 1][k + 1];

        for(int j = 0; j <= n; j++){
            ksum[0][j][0] = 1;
        }

        for(int i = 1; i <= target; i++){
            for(int j = 1; j <= n; j++){
                for(int l = 1; l <= j && l <= k; l++){
                    ksum[i][j][l] = ksum[i][j - 1][l];
                    if(i - A[j - 1] >= 0){
                        ksum[i][j][l] += ksum[i - A[j - 1]][j - 1][l - 1];
                    }
                }
            }
        }

        return ksum[target][n][k];
    }
}