题目

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.

Tags Expand
LintCode Copyright Dynamic Programming

解题思路

• 思路一： 迭代，开始时依次选择一个点，然后根据新的target值和新的数组，选择k-1个数，思路直接简单。但是存在重复计算。该算法复杂度为 ${N^k }$ ,指数递增，所以在lintcode中就计算超时了。
• 思路二：参考网上解法，还记得我们求解一堆数，任意个数的合为N的组合个数的题吗？当时用一个一维数组来存储可以构成的数，现在我们同样用一个长度为target的数据来存储数据，存的是前j个数中选择i个数，和的构成分布，所以数据就是dp[i][j][target]，加上下届即可。
  dp[i][j][v]=dp[i][j-1][v]+dp[i-1][j-1][v-A[i]]

代码

代码一

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

        if(k == 1){
            for(int i=0;i<A.length;i++)
                if(A[i] == target)
                    return 1;
            return 0;
        }
        else  {
            int[] B = new int[A.length - 1];
            if (A.length > 1)
                System.arraycopy(A, 1, B, 0, A.length - 1);
            return kSum(B, k - 1, target - A[0]) + kSum(B, k, target);
        }
    }
}

代码二

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) {
        int[][][] dp = new int[k + 1][A.length + 1][target + 1];

        for (int i = 1; i <= A.length; i++) {
            for (int j = i; j > 0; j--) {
                if (A[j - 1] <= target)
                    dp[1][i][A[j - 1]] = 1;
            }
        }

        for (int m = 2; m <= k; m++) {
            for (int n = m; n <= A.length; n++) {
                for (int l = 0; l <= target; l++) {
                    dp[m][n][l] = dp[m][n][l] + dp[m][n - 1][l];
                    if (l + A[n - 1] <= target)
                        dp[m][n][l + A[n - 1]] = dp[m][n][l + A[n - 1]] + dp[m - 1][n - 1][l];
                }
            }
        }

        return dp[k][A.length][target];
    }
}