k Sum

Description

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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 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
        if (A.empty() || A.size() < k) {
            return 0;
        }
        int len = A.size();
        vector<vector<vector<int>>> 
            dp(len + 1, vector<vector<int>>(k + 1, vector<int>(target + 1, 0)));
        // init
        // for k = 0. target = 1. we have one solution, not select any one
        for (int i = 0; i < len + 1; ++i) {
            dp[i][0][0] = 1;
        }
        // for normal condition
        for (int ia = 1; ia < len + 1; ++ia) {
            for (int ik = 1; ik < k + 1; ++ik) {
                for (int it = 1; it < target + 1; ++it) {
                    // Obviously, for index ia, the solution is ">=" the prev one
                    dp[ia][ik][it] = dp[ia-1][ik][it];
                    // if the target can afford A[ia-1]
                    // the solution need to extended
                    // use A[ia-1] and target [it-A[ia-1]]
                    if (it >= A[ia-1]) {
                        dp[ia][ik][it] += dp[ia-1][ik-1][it-A[ia-1]];
                    }
                }
            }
        }
        // cout << "Target / Solution " << endl;
        // for (int i = 0; i < target + 1; ++i) {
        //     cout << i << " " << dp[len][k][i] << endl;
        // }
        return dp[len][k][target];
    }
};

Similar problems

x

Tags

x