K SUM

Solution

n个数，取k个数，组成和为target

            不取这个数         去这个数

f[i][k][j] = f[i-1][k][j] + f[i-1][k-1][j-A[i]];

Code

/**

 * @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
    if(A.size() == 0)
    {
        return 0;
    }

    vector<vector<vector<int>>> dp;
    for(int i = 0; i <= A.size(); i++)
    {
        vector<vector<int>> tmp2;
        for(int j = 0; j <= k; j++)
        {
            vector<int> tmp(target+1, 0);
            tmp2.push_back(tmp);
        }
        tmp2[0][0] = 1;
        dp.push_back(tmp2);
    }

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

    return dp[A.size()][k][target];
}