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:
x ≠ y and z > 0.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.
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);
}