forked from cmhungsteve/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
optimal-account-balancing.cpp
48 lines (45 loc) · 1.46 KB
/
optimal-account-balancing.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
// Time: O(n * 2^n), n is the size of the debt.
// Space: O(n * 2^n)
class Solution {
public:
int minTransfers(vector<vector<int>>& transactions) {
unordered_map<int, int> account;
for (const auto& transaction : transactions) {
account[transaction[0]] += transaction[2];
account[transaction[1]] -= transaction[2];
}
vector<int> debt;
for (const auto& kvp : account) {
if (kvp.second) {
debt.emplace_back(kvp.second);
}
}
if (debt.empty()) {
return 0;
}
const auto n = 1 << debt.size();
vector<int> dp(n, numeric_limits<int>::max()), subset;
for (int i = 1; i < n; ++i) {
int net_debt = 0, number = 0;
for (int j = 0; j < debt.size(); ++j) {
if (i & 1 << j) {
net_debt += debt[j];
++number;
}
}
if (net_debt == 0) {
dp[i] = number - 1;
for (const auto& s : subset) {
if ((i & s) == s) {
if (dp[s] != numeric_limits<int>::max() &&
dp[i - s] != numeric_limits<int>::max()) {
dp[i] = min(dp[i], dp[s] + dp[i - s]);
}
}
}
subset.emplace_back(i);
}
}
return dp.back();
}
};