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.
```

465. Optimal Account Balancing
``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn min_transfers(transactions: Vec<Vec<i32>>) -> i32 {
let mut balance: HashMap<i32, i32> = HashMap::new();
for t in transactions {
*balance.entry(t).or_default() -= t;
*balance.entry(t).or_default() += t;
}
let mut debts = vec![];
for &v in balance.values() {
if v != 0 {
debts.push(v);
}
}
let n = debts.len();
let mut res = std::usize::MAX;
Self::dfs(0, 0, &mut debts, &mut res, n);
res as i32
}

fn dfs(start: usize, cur: usize, debts: &mut Vec<i32>, min: &mut usize, n: usize) {
if start == n {
*min = cur.min(*min);
} else {
if debts[start] == 0 {
Self::dfs(start + 1, cur, debts, min, n);
} else {
let transaction = debts[start];
debts[start] -= transaction;
for i in start + 1..n {
if debts[i] * transaction < 0 {
debts[i] += transaction;
Self::dfs(start + 1, cur + 1, debts, min, n);
debts[i] -= transaction;
}
}
debts[start] += transaction;
}
}
}
}

#[test]
fn test() {
let transactions = vec_vec_i32![[0, 1, 10], [2, 0, 5]];
let res = 2;
assert_eq!(Solution::min_transfers(transactions), res);
let transactions = vec_vec_i32![[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]];
let res = 1;
assert_eq!(Solution::min_transfers(transactions), res);
}
``````