forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
shopping-offers.cpp
31 lines (25 loc) · 978 Bytes
/
shopping-offers.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
// Time: O(n * 2^n)
// Space: O(n)
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return shoppingOffersHelper(price, special, needs, 0);
}
private:
int shoppingOffersHelper(const vector<int>& price, const vector<vector<int>>& special, vector<int>& needs, int i) {
if (i == special.size()) {
return inner_product(price.begin(), price.end(), needs.begin(), 0);
}
int result = shoppingOffersHelper(price, special, needs, i + 1);
for (int j = 0; j < needs.size(); ++j) {
needs[j] -= special[i][j];
}
if (all_of(needs.begin(), needs.end(), [](int i) { return i >= 0; })) {
result = min(result, special[i].back() + shoppingOffersHelper(price, special, needs, i));
}
for (int j = 0; j < needs.size(); ++j) {
needs[j] += special[i][j];
}
return result;
}
};