给定 n 个不同的正整数，整数 k （ k <= n ）以及一个目标数字 target 。　 在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？

样例 1

输入: List = [1,2,3,4] k = 2 target = 5 输出: 2 说明: 1 + 4 = 2 + 3 = 5 

样例 2

输入: List = [1,2,3,4,5] k = 3 target = 6 输出: 1 说明: 只有这一种方案。1 + 2 + 3 = 6 

算法：dp

如果没有 k 的约束。我们可以发现，这题就可以转化为背包问题。利用 n 个正整数达到目标 target 。那么有了 k 的约束之后，我们需要用额外的一维来维护使用的数字。所以约定状态如下，用 dp[i][j][k]表示前 ii 个数里选 j 个和为 k 的方案数。

• 假定 dp[i][j][k]之前的方案数都已知，考虑 dp[i][j][k]的情况。
• dp[i][j][k]可以由 dp[i−1][j−1][k−A[i−1]]的状态取 A[i-1]得到。
• dp[i][j][k]也可以由 dp[i−1][j][k]直接得到，即不取 A[i-1]。
• 最后返回 f[n][k][target]即可。

复杂度分析

• 时间复杂度 O(n∗k∗target)O(n∗k∗target)
• 空间复杂度 O(n∗k∗target)O(n∗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 n = A.length;         int[][][] f = new int[n + 1][k + 1][target + 1];         for (int i = 0; i < n + 1; i++) {             f[i][0][0] = 1;         }         for (int i = 1; i <= n; i++) {             for (int j = 1; j <= k && j <= i; j++) {                 for (int t = 1; t <= target; t++) {                     f[i][j][t] = 0;                     if (t >= A[i - 1]) {                         f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];                     }                     f[i][j][t] += f[i - 1][j][t];                 } // for t             } // for j         } // for i         return f[n][k][target];     } }