Problem

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.

Examples

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6
7
8
9

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.

Solution

Method 1 – Bitmask Dynamic Programming for Debt Settlement

Intuition

To minimize the number of transactions to settle all debts, we first compute each person’s net balance. We then use dynamic programming with bitmasking to find the optimal way to group zero-sum subsets, minimizing the number of transactions needed.

Approach

  1. Calculate each person’s net balance from all transactions.
  2. Filter out zero balances; only non-zero balances need to be settled.
  3. Use DP with bitmasking: for each subset of balances, if their sum is zero, they can be settled with (size - 1) transactions.
  4. For each subset, try all possible partitions to minimize the total transactions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        int g[12]{};
        for (auto& t : transactions) {
            g[t[0]] -= t[2];
            g[t[1]] += t[2];
        }
        vector<int> nums;
        for (int x : g) {
            if (x) {
                nums.push_back(x);
            }
        }
        int m = nums.size();
        int f[1 << m];
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i < 1 << m; ++i) {
            int s = 0;
            for (int j = 0; j < m; ++j) {
                if (i >> j & 1) {
                    s += nums[j];
                }
            }
            if (s == 0) {
                f[i] = __builtin_popcount(i) - 1;
                for (int j = (i - 1) & i; j; j = (j - 1) & i) {
                    f[i] = min(f[i], f[j] + f[i ^ j]);
                }
            }
        }
        return f[(1 << m) - 1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func minTransfers(transactions [][]int) int {
    g := [12]int{}
    for _, t := range transactions {
        g[t[0]] -= t[2]
        g[t[1]] += t[2]
    }
    nums := []int{}
    for _, x := range g {
        if x != 0 {
            nums = append(nums, x)
        }
    }
    m := len(nums)
    f := make([]int, 1<<m)
    for i := 1; i < 1<<m; i++ {
        f[i] = 1 << 29
        s := 0
        for j, x := range nums {
            if i>>j&1 == 1 {
                s += x
            }
        }
        if s == 0 {
            f[i] = bits.OnesCount(uint(i)) - 1
            for j := (i - 1) & i; j > 0; j = (j - 1) & i {
                f[i] = min(f[i], f[j]+f[i^j])
            }
        }
    }
    return f[1<<m-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int minTransfers(int[][] transactions) {
        int[] g = new int[12];
        for (var t : transactions) {
            g[t[0]] -= t[2];
            g[t[1]] += t[2];
        }
        List<Integer> nums = new ArrayList<>();
        for (int x : g) {
            if (x != 0) {
                nums.add(x);
            }
        }
        int m = nums.size();
        int[] f = new int[1 << m];
        Arrays.fill(f, 1 << 29);
        f[0] = 0;
        for (int i = 1; i < 1 << m; ++i) {
            int s = 0;
            for (int j = 0; j < m; ++j) {
                if ((i >> j & 1) == 1) {
                    s += nums.get(j);
                }
            }
            if (s == 0) {
                f[i] = Integer.bitCount(i) - 1;
                for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
                    f[i] = Math.min(f[i], f[j] + f[i ^ j]);
                }
            }
        }
        return f[(1 << m) - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    fun minTransfers(transactions: List<List<Int>>): Int {
        val g = IntArray(12)
        for ((f, t, x) in transactions) {
            g[f] -= x
            g[t] += x
        }
        val nums = g.filter { it != 0 }
        val m = nums.size
        val f = IntArray(1 shl m) { Int.MAX_VALUE / 2 }
        f[0] = 0
        for (i in 1 until (1 shl m)) {
            var s = 0
            for (j in 0 until m) {
                if ((i shr j) and 1 == 1) s += nums[j]
            }
            if (s == 0) {
                f[i] = Integer.bitCount(i) - 1
                var j = (i - 1) and i
                while (j > 0) {
                    f[i] = minOf(f[i], f[j] + f[i xor j])
                    j = (j - 1) and i
                }
            }
        }
        return f[(1 shl m) - 1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from collections import defaultdict
from math import inf
class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        g = defaultdict(int)
        for f, t, x in transactions:
            g[f] -= x
            g[t] += x
        nums = [x for x in g.values() if x]
        m = len(nums)
        f = [inf] * (1 << m)
        f[0] = 0
        for i in range(1, 1 << m):
            s = 0
            for j, x in enumerate(nums):
                if i >> j & 1:
                    s += x
            if s == 0:
                f[i] = i.bit_count() - 1
                j = (i - 1) & i
                while j > 0:
                    f[i] = min(f[i], f[j] + f[i ^ j])
                    j = (j - 1) & i
        return f[-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

pub struct Solution;
impl Solution {
    pub fn min_transfers(transactions: Vec<Vec<i32>>) -> i32 {
        let mut g = [0; 12];
        for t in &transactions {
            g[t[0] as usize] -= t[2];
            g[t[1] as usize] += t[2];
        }
        let nums: Vec<i32> = g.iter().cloned().filter(|&x| x != 0).collect();
        let m = nums.len();
        let mut f = vec![i32::MAX / 2; 1 << m];
        f[0] = 0;
        for i in 1..(1 << m) {
            let mut s = 0;
            for j in 0..m {
                if (i >> j) & 1 == 1 {
                    s += nums[j];
                }
            }
            if s == 0 {
                f[i] = (i.count_ones() as i32) - 1;
                let mut j = (i - 1) & i;
                while j > 0 {
                    f[i] = f[i].min(f[j] + f[i ^ j]);
                    j = (j - 1) & i;
                }
            }
        }
        f[(1 << m) - 1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

function minTransfers(transactions: number[][]): number {
    const g: number[] = new Array(12).fill(0);
    for (const [f, t, x] of transactions) {
        g[f] -= x;
        g[t] += x;
    }
    const nums = g.filter(x => x !== 0);
    const m = nums.length;
    const f: number[] = new Array(1 << m).fill(1 << 29);
    f[0] = 0;
    for (let i = 1; i < 1 << m; ++i) {
        let s = 0;
        for (let j = 0; j < m; ++j) {
            if (((i >> j) & 1) === 1) {
                s += nums[j];
            }
        }
        if (s === 0) {
            f[i] = bitCount(i) - 1;
            for (let j = (i - 1) & i; j; j = (j - 1) & i) {
                f[i] = Math.min(f[i], f[j] + f[i ^ j]);
            }
        }
    }
    return f[(1 << m) - 1];
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Complexity

  • ⏰ Time complexity: O(3^N), where N is the number of people with non-zero balance. This comes from trying all possible subsets and partitions of debts, as each person can be included, excluded, or paired in each subset.
  • 🧺 Space complexity: O(2^N), for the DP array that stores the minimum transactions for each subset of debts.