lintcode k数和

给定n个不同的正整数，整数k（k < = n）以及一个目标数字。　　　　
在这n个数里面找出K个数，使得这K个数的和等于目标数字，求问有多少种方案？
样例
给出[1,2,3,4]，k=2， target=5，[1,4] and [2,3]是2个符合要求的方案
题目链接：http://www.lintcode.com/zh-cn/problem/k-sum/

这类问题一般都是使用动态规划的方法。建立到一个三维数组dp[i][j][k]表示在前i个数里取j个数和为k的方案数，于是dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-A[i]]，即包括A[i]和不包括A[i]的两种方案。可以看到i只跟i-1有关，所以我们可以把三维数组变成二维数组，把第一维去掉。

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        // wirte your code here
        vector<vector<int> > dp(k + 1,vector<int>(target + 1,0));
        dp[0][0] = 1;
        for (auto num : A) {
            for (int i = k;i >= 1;i--) {
                for (int j = target;j >= num;j--) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[k][target];
    }
};