Minimum Number of Transactions to Settle Debts

Problem Preview

"A debt tracking app records transactions showing who paid whom and how much. Each transaction includes a borrower, a lender, and an amount. Given a list of transactions, determine the minimum number of transactions required to settle all debts. ### Problem Suppose the number of people (n) = 3, the number of transactions (m) = 4, and transactions = [[0, 1, 20], [1, 2, 10], [2, 0, 10], [0, 1, 5]]. Each transaction is represented as [from, to, amount], meaning: - Person 0 owes person 1 $20 - Person 1 owes person 0 $5 - Person 1 owes person 2 $10 - Person 2 owes person 0 $10 After simplification, only one transaction is needed: Person 0 pays $15 to person 1. Therefore, the minimum number of transactions required is 1. ### Input - n: The number of people. - debt: A 2D array representing the debt between people. ### Output - The minimum number of transactions required to settle all debts. ### Constraints - 2 ≤ n ≤ 9 - 2 ≤ m ≤ 10^5 - 0 ≤ debt[i][j] < n - 1 ≤ debt[i][j] ≤ 10^9"