LintCode 89: k Sum (背包问题)

89 · k Sum
Algorithms
Hard

Description
Given n distinct positive integers, integer k (k \leq n)(k≤n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example
Example 1:

Input:

A = [1,2,3,4]
k = 2
target = 5
Output:

2
Explanation:

1 + 4 = 2 + 3 = 5
Example 2:

Input:

A = [1,2,3,4,5]
k = 3
target = 6
Output:

1
Explanation:

There is only one method. 1 + 2 + 3 = 6

Tags
Related Problems

90
k Sum II
Medium

1689
k Sum III
Medium

解法1: 套用subset模板，但最后会超时。

class Solution {
public:
    /**
     * @param a: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integer
     */
    int kSum(vector<int> &a, int k, int target) {
        int pos = 0, solSum = 0, totalNum = 0;
        vector<int> sol;
        helper(a, k, target, pos, sol, solSum, totalNum);
        return totalNum;
    }
private:
    void helper(vector<int> &a, int k, int target, int pos, vector<int>& sol, int sum, int &totalNum) {
        if (sol.size() > k) return;
        if (sol.size() == k && sum == target) {
            totalNum++;
            return;
        }        
        for (int i = pos; i < a.size(); i++) {
            sol.push_back(a[i]);
            helper(a, k, target, i + 1, sol, sum + a[i], totalNum);   
            sol.pop_back();
        }
        return;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

解法2：转换成背包问题，注意因为有k的限制，所以多了一维。

class Solution {
public:
    /**
     * @param a: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integer
     */
    int kSum(vector<int> &a, int k, int target) {
        int len = a.size();
        
        //dp[a][b][c]: 前a个数字里面找出b个，其sum为c的方案个数。
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(k + 1, vector<int>(target + 1, 0))); 
       
        for (int i = 0; i <= len; i++) {
            dp[i][0][0] = 1;
        }
       
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    dp[i][j][t] = dp[i - 1][j][t];
                    if (t >= a[i - 1]) dp[i][j][t] += dp[i - 1][j - 1][t - a[i - 1]];
                }
            }
        }
        return dp[len][k][target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

滚动数组优化空间复杂度到O(k*target):

class Solution {
public:
    /**
     * @param a: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integer
     */
    int kSum(vector<int> &a, int k, int target) {
        int len = a.size();
        
        //dp[a][b][c]: 前a个数字里面找出b个，其sum为c的方案个数。
        vector<vector<vector<int>>> dp(2, vector<vector<int>>(k + 1, vector<int>(target + 1, 0))); 
       
        for (int i = 0; i <= len; i++) {
            dp[i % 2][0][0] = 1;
        }
       
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    dp[i % 2][j][t] = dp[(i - 1) % 2][j][t];
                    if (t >= a[i - 1]) dp[i % 2][j][t] += dp[(i - 1) % 2][j - 1][t - a[i - 1]];
                }
            }
        }
        return dp[len % 2][k][target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

另一种空间优化方案。

class Solution {
public:
    /**
     * @param a: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integer
     */
    int kSum(vector<int> &a, int k, int target) {
        int len = a.size();
        
        //dp[k][t]: 找出k个数字，其sum为t的方案个数。//这a个数字可以是vector a里面的任意k个
        vector<vector<int>> dp(k + 1, vector<int>(target + 1, 0)); 
       
        for (int i = 0; i <= k; i++) {
            dp[0][0] = 1;
        }
       
        for (int i = 1; i <= len; i++) {
            for (int j = min(i, k); j >= 1; j--) {
                for (int t = target; t >= 1; t--) {
                    dp[j][t] = dp[j][t];
                    if (t >= a[i - 1]) dp[j][t] += dp[j - 1][t - a[i - 1]];
                }
            }
        }
        return dp[k][target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29