## 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:**

- A transaction will be given as a tuple (x, y, z). Note that
`x ≠ y`

and`z > 0`

. - 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:2Explanation: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:1Explanation: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.

## Rust Solution

```
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[0]).or_default() -= t[2];
*balance.entry(t[1]).or_default() += t[2];
}
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);
}
```

Having problems with this solution? Click here to submit an issue on github.