-
Notifications
You must be signed in to change notification settings - Fork 22
/
89.k-sum.cpp
72 lines (68 loc) · 1.5 KB
/
89.k-sum.cpp
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Tag: Backpack DP, Dynamic Programming/DP
// Time: O(NKT)
// Space: O(NKT)
// Ref: -
// Note: -
// Given `n` distinct positive integers, integer `k` $(k \leq n)$ and a number `target`.
//
// Find `k` numbers where sum is target.
// Calculate how many solutions there are?
//
// **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
//
//
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) {
// write your code here
int n = a.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (k + 1, vector<int>(target + 1, 0)));
dp[0][0][0] = 1;
for (int i = 1; i <=n; i++) {
for (int j = 0; j <= k; j++) {
for (int t = 0; t <= target; t++) {
dp[i][j][t] = dp[i - 1][j][t];
if (j - 1 >= 0 && t - a[i - 1] >= 0) {
dp[i][j][t] += dp[i - 1][j - 1][t - a[i - 1]];
}
}
}
}
return dp[n][k][target];
}
};