# 465. Optimal Account Balancing

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as `[[0, 1, 10], [2, 0, 5]]`.

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

**Note:**

1. A transaction will be given as a tuple (x, y, z). Note that `x ≠ y` and `z > 0`.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.

**Example 1:**

```
Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
```

**Example 2:**

```
Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.
```

```cpp
// DFS
void helper(vector<int>& account, int start, int cnt, int& res) {
    int n = account.size();
    while (start < n && account[start] == 0) ++start;
    if (start == n) {
        res = min(res, cnt);
        return;
    }
    for (int i = start + 1; i < n; ++i) {
        if (account[i] * account[start] < 0) {
            account[i] += account[start];
            helper(account, start + 1, cnt + 1, res);
            account[i] -= account[start];
        }
    }
}
int minTransfers(vector<vector<int>>& transactions) {
    unordered_map<int, int> balance;
    int res = numeric_limits<int>::max();
    for (const vector<int>& t : transactions) {
        balance[t[0]] -= t[2]; // lend
        balance[t[1]] += t[2]; // borrow
    }
    vector<int> account;
    for (auto& e : balance) {
        if (e.second != 0) account.push_back(e.second);
    }
    helper(account, 0, 0, res);
    return res;
}
```

```cpp
// Dynamic Programming
// https://leetcode.com/problems/optimal-account-balancing/discuss/219187/Short-O(N-*-2N)-DP-solution-with-detailed-explanation-and-complexity-analysis
int minTransfers(vector<vector<int>>& transactions) {
    unordered_map<int, int> balance; // person_id -> balance
    for (auto& t: transactions) {
        balance[t[0]] -= t[2]; // lend
        balance[t[1]] += t[2]; // borrow
    }
    vector<int> account; // all non-zero balances
    for (auto& [_, b]: balance) {
        if (b) account.push_back(b);
    }
    const int n = account.size();
    vector<int> dp(1 << n); // max zero sum groups
    vector<long> sums(1 << n);
    for (int bitmask = 1; bitmask < (1 << n); ++bitmask) {
        for (int i = 0; i < n; ++i) {
            if (bitmask & (1 << i)) continue;
            int next = bitmask | (1 << i); // set bit
            sums[next] += account[i];
            if (sums[bitmask] == 0) dp[next] = max(dp[next], dp[bitmask] + 1);
            else dp[next] = max(dp[bitmask], dp[next]);
        }
    }
    return n - dp.back();
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/465.-optimal-account-balancing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.