Mobile money vector created by pch.vector — www.freepik.com

生活中的智慧，分錢背後藏著的經典演算法

有一天，A、B、C 三個人出外旅遊，由於過程中有時候會忘記帶錢包，朋友之間當然就會互相借一下，假設情境如下

A 借 B：50元

B 借 C：50 元

當旅行結束，要結清欠款時，該怎麼做呢？一個簡單的做法就是全部反過來

B 還 A：50 元

C 還 B：50 元

但如果簡單觀察一下，我們其實有更有效率的做法，只要一個步驟即可

C 還 A：50 元

所以有趣的問題就來了

若給定一組人與這組人之間的金錢交換關係，則最少需要幾個步驟，才能全數結清。

看起來很簡單的敘述，生活中也很常見，但意外的是並不容易，用演算法的角度來說的話，就是找不到簡單的 Linear Time 的做法。

先讓我們簡化一下問題，並看幾個例子。我們可以把所有人的錢的最後增減狀態記錄下來，以上面那個簡單的例子來說，出遊結束後的最後狀態就是

A: -50, B: 0, C: 50，用一個 Array 可以記錄成 [-50, 0, 50]。

而我們的目標就是讓所有人的狀態都歸零，此時一眼就可以看出，最有效率的做法，就是 index = 2 的那個人，把 50 元還給 index = 0 的那個人即可，只需一個步驟。

讓我們再看看幾個不同例子：

1. [-50, -30, 30, 50]：最少步驟為 2

2. [-220, -200, -30, 220, 230]：最少步驟為 3

3. [3, 3, 3, 3, -4, -4, -4,]：最少步驟為 6（這個最麻煩，可以想想怎麼處理）

有興趣的讀者可以試著再想幾個例子，然後你會發現真的沒有很簡單的規律可循，例如先排序後，正數最大的給負數最大的人錢，依序處理，這種簡單的 Greedy 想法基本都是行不通的，所以到底該怎麼做呢？

經過一番研究後，發現這是個很有層次的問題，當人數少的時候，可以用較為暴力的做法（但也已經不容易），而人數多起來，則得用上更複雜的演算法才能處理。讓我們依序來看看，這題由簡入深的三種解法，分別可以處理不同量級的人數，也順便從這個生活小例子，認識不同演算法的威力。

Backtracking O(N!)：適合人數小於 10

難度約為 Leetcode Medium

如果我們僅有 10人，可以用所謂的窮舉法，意思就是把所有可能的分錢方式都確認一遍，最後找尋最小的那個。但這種類型的窮舉方式就是 backtracking 演算法，如果對他不熟的人，可以先看看我之前寫的這篇介紹。

思路是這樣，我把所有人現在錢包的狀態一字排開，用一個 array 表示，index 代表第幾個人，值為正數代表他還欠別人多少，負數則代表別人要還他多少錢。

例如 [30, 20, -10, -40]，代表 0 號欠了 30 元，1 號欠 20 元，2 號要拿回 10元，3 號要拿回 40 元。

我們的窮舉方式，就是依序一個個結清歸零，方式如下：

一開始從 0 號開始做結清，步驟如下

1. 從後面任意挑選一個人（先假設挑到 3 號）
2. 此時假如 0 號欠 x 元，那他就把 x 元還給 3 號，反之，則是跟 3 號要回 x 元。（注意：這邊是不管 3 號的狀態的，我們只管先結清 0 號就好，3 號按照順序之後再來處理）
3. 把步驟數加 1

以上講起來很囉嗦，用程式寫起來很簡單，就是：

amounts[3] += amounts[0]
step += 1

Note：不管 amounts[0] 是正還是負，寫起來都是這樣，可以想想為什麼？

當然，由於我們並不知道當下給誰才是最好的，因此最暴力直白的做法就是，每個人我都試試看，並將結清後的 amounts 暫時狀態保留，一路依序做下去直到全部人都被結清結束。以下示範其中一種可能的結清過程。

1. 初始狀態：[30, 20, -10, -40]
2. 0 號結清：0 號把錢給 3 號，狀態變成 [0, 20, -10, -10]，步驟數變為 1
3. 1 號結清：1 號把錢給 2 號，狀態變成 [0, 0, 10, -10]，步驟數變為 2
4. 2 號結清：2 號把錢給 3 號，狀態變成 [0, 0, 0, 0]，步驟數變為 3
5. 到此為止，全數完成，本次過程總步驟數為 3

Note：不管每次結清時挑到誰（只要是挑排在他後面的人即可），最後一定都會全部歸零的，可以想想為什麼？

當然只嘗試一種結清方式是不夠的，所以我們要一次次的反覆（backtrack）回原本狀態，再找另一個人試試看，如此不斷循環。這就是用 backtracking 做窮舉的精神，於是我們會寫出一個類似下面這樣的結構。

def backtracking(index, step): # 假設現在要結清的是 0 號，index 就是 0
    for i in range(index + 1, N):
        amounts[i] += amounts[index] # 試試看把錢與第 i 個人結清
        backtracking(index + 1, step + 1) # 用現在的狀態，繼續依序處理下一個人，並把步驟數加 1
        amounts[i] -= amounts[index] # 上一個 i 號嘗試完了，把狀態還原

但很多細節要再加進去

1. 如果輪到某個人的時候，他的錢包剛好也已經被結清歸零了，那我們可以直接跳過他，例如某個人需要拿回 30，剛好被更前面某個欠 30 的人還給他補滿了，那他現在的狀態是沒有需要做任何操作的，如此一來，我們就省一下一個操作了！所謂比較好的流程，其實就是盡可能中途有更多這種情況發生。
2. 如果當前這個人是欠款的，我們其實不會讓他跟另一個也是欠錢的人去結清，因為很顯然這樣沒有意義，例如我欠了 30，另一個人欠 50，那我把自己的 30 給他，只是讓他變成欠 80，之後他還是得再把這些錢，轉給那些需要被償還的人，只是徒然增加操作步驟而已（同理，兩人都要拿錢也一樣）
3. 如果 index 已經超過最後一個人，代表這一次的嘗試已經完成，則我們看一下當下的步驟總數，如果出現更小的步驟數則更新答案。

最終我們完整的 backtracking 程式碼就長這樣了

這樣做法，理論上的時間複雜度不好估計，因為到底每個人需要嘗試多少不同的人，會根據測試資料改變。但可以估個上限，假設每個人都需要嘗試所有後面的人。假設現在五個人，第一個要嘗試 4 種可能，第二個人嘗試 3 種，第三個嘗試 2 種… 依此類推，大概是 (N-1)! 的數量級。我們可以把時間複雜度算成 O(N!)。但實際上我們只嘗試正負號相反的人，而且會挑掉已經歸零的人，所以會再快很多。

Dynamic Programming O(N * 2 ^ N)：適合人數小於 30

難度約為 Leetcode Hard

如果人數到達這個數量級，難度就會上升了，必須使用動態規劃的做法。其實上面的暴力窮舉做法中，已經點出了關鍵處，就是

我們希望在整個交換的流程中，盡可能出現有些人在輪到時，已經被結清了，每出現一次這種狀況，我們就可以省略一個步驟

這是什麼狀況呢？一樣給大家看個實際例子

1. 初始狀態：[-220, -200, -30, 220, 230]
2. 0 號結清：0 號把錢給 3 號，狀態變成 [0, -200, -30, 0, 230]，步驟數為 1
3. 1 號結清：1 號把錢給 4 號，狀態變成 [0, 0, -30, 0, 30]，步驟數為 2
4. 2 號結清：2 號把錢給 4 號，狀態變成 [0, 0, 0, 0, 0]，步驟數為 3
5. 3 號結清：但 3 號此時已經是 0 了！（剛剛 0 號已經幫他歸零了），所以直接跳過
6. 4 號結清：4 號也已經是 0 了（1 號與 2 號已經幫他結清了），一樣跳過
7. 最終我們僅需 3 步驟

但怎樣能讓這種事盡可能發生呢？想法其實也不難，那就是

我們盡可能的讓能夠互相結清的人湊成一組，依序解決

再以上面的例子看一次，[-220, -200, -30, 220, 230] 裡面，-220 與 220 可以自成一組，而 -200, -30, 230 三個也可以自成一組，因此我們將它分成兩組 [-220, 220], [-200, -30, 230]，這兩組之間互相不需要干涉，各自解決即可。因此我們的第一個重點目標就是

盡可能將這樣的組分到最細，直到每一個小組之間都不可再分割為止

例如以下

1. [-30, -20, -10, 10, 20, 30] 就會分三組 [-10, 10], [-20, 20], [-30, 30]
2. [-100, 50, 50, -200, 100, 100] 就會分成 [-100, 50, 50], [-200, 100, 100]，當然你也可以分成 [-100, 100], [-200, 50, 50, 100]。兩者皆可
3. [3, 3, 3, 3, -4, -4, -4] 則不可再分割了

接著，第二個重點來了

每一個不可再分割的組之內，需要結清的最小步驟數，就是組員數減 1

這件事可以回到原本 backtracking 的步驟數去想，如果這個小組之間，已經完全不可能出現中途有人先被結清的狀況，則我們唯一能做的，就是一個一個照順序結清下去，不會有任何人能被跳過，因此最後總步驟數一定是人數減 1，可以拿以上任何一個小例子試試。

當然有一個特殊狀況，就是如果有些人一開始變化就是 0，那我們從一開始就該把他排除掉，因為他完全沒有參與到各著分錢與結清的過程

因此，我們的做法與答案已經出來了，那就是

若總人數為 N（其 amounts 皆不等於 0），且我們最多能將其分成 M 個不可再分割的小組，則最小步驟數會等於 N-M

舉個例子，我們有 10 個人 (N=10)，若最多能分成 3 組 (M=3)，大小分別為 2, 3, 5，而這三個組各自要結清，分別需要 2–1, 3–1, 5–1 個步驟，也就等於 2+3+5–(3*1) = N-M

因此我們原始的問題，可以轉換成以下更單純的問題了

找到最大可分割的小組數量 M，每個小組內部都可以結清款項。

而這是一個經典的動態規劃問題，會用到 bitmasking 的技巧。做法是這樣的，我們把每一種”現在已經挑選的群組”用 0 與 1 的 bit masking 方式表示。假設現在有五個人（編號為 0 號～4 號）

00110：代表挑選了 1 號、2 號

11001：代表我們挑選了 0 號、3 號、4 號

11111：代表全選

而這樣的二進位組合，又可以用 10 進位的整數來表示，如下

00110：在十進位是 6

11001：在十進位就是 25

11111：在十進位是 31

另外我們給兩個 array，分別是 sum_value 與 dp，而其 index 稱之為 state，會以十進位表示，但代表的就是他對應的二進位所代表的組合

sum_value[state]：代表某個組合 state 中，全部人欠款與待還款相加總數

dp[state]：代表某個組合 state 中，最多含有幾個各自能結清的群組

舉例來說

1. sum_value[6]：代表 00110 這個組合中款項的總和，也就是 amounts[1] + amounts[2]
2. dp[31]：代表 11111 這五個人，最多能被切出來幾個小組，這些小組 group 的 sum_value[group] 必須為 0

再次看一個真實數字的例子：[-220, -200, -30, 220, 230]，以這個例子來說

sum_value[9] = 0（9 => 01001 => amounts[0] + amounts[3] = 0)

sum_value[22] = 0（22 => 10110 => amounts[1] + amounts[2] + amounts[4] = 0)

dp[9] = 1 （僅此一組，無法再拆）

dp[22] = 1（僅此一組，無法再拆）

dp[31] = 2（因為可以拆成兩組 9 與 22，其 sum_value 都是零）

到此為止，已經快接近答案了，我們將要寫下最重要的 dp 轉移方程式了，也就是某個狀態，與前一個狀態的關聯性。

假設現在的狀態是 11001（稱之為 current_state），而少掉一個人則是上一個狀態（last_state），現在來說，有三個可能的上一個狀態，分別是，11000、10001、01001 三種（統稱為 last states），則我們首先要找到上一個狀態中，切割總數最多的那個。

max_group_cnt = max([dp[last_state] for all possible last states])

這個數字，就是我們現在狀態 dp[current_state] 最少會有的組數，畢竟如果有某個”可能的上一個狀態”已經可以切割出 k 組各自結清的 group 了，那現在又多一個人，最少最少也一樣有 k 組對吧！

但，有沒有可能更多呢？有，答案是只要 sum_value[current_state] = 0，我們就又多了一組出來。

可以這樣想，只要現在狀態的 sum_value[current_state] = 0，那他少一個人的 sum_value[last_state] 一定不為 0。

舉例來說，假如上一個狀態 last_state 是 [-30, -20, -10, 10, 20]，這裡面已經有 2 個小組 [-10, 10], [-20, 20]，另外剩下一個 [-30] 搞不定。但現在多加一個人後，current_state 的總和居然歸零了，代表新的這個人一定剛好是 [30]，並且還湊出了新的一對 [-30, 30]。反之，如果現在狀態總和仍然不是 0，則顯然我們能切出來的小組總數，就是跟之前一樣而已。

因此最核心的轉移式終於出來了

max_group_cnt = max([dp[last_state] for all possible last states])
if sum_value[current_state] == 0:
    dp[current_state] = max_group_cnt + 1
else:
    dp[current_state] = max_group_cnt

最終完整程式碼如下，其實並不長，但需要具備的知識與巧思多了一些

最終時間複雜度倒是很好計算，外層迴圈遍歷了所有可能狀態，就是 2 的 N 次方，內層迴圈則遍歷人數，就是 N，因此總時間複雜度為 O(N * 2^N)

到此為止，以上兩個解法，其實只有算出”最小步驟數”，至於具體每個步驟內容是怎樣，我並沒有寫出來。不過如果你上面兩個都看的懂，應該不難透過一些加工調整去回溯路徑，就能把詳細步驟也印出來，但因為 code 會更冗長，就先不贅述了。

另外，以上都是 non-linear time 的做法，人數限制仍然很嚴格，目前我還沒找到能在 linear time 解決的方法，但我有找到一篇文章，參考了知名分錢 app Splitwise 官方介紹的觀念後，提出了一個有點複雜的做法，雖然未必能找到最佳解，但仍是個能高效率大幅化簡步驟的厲害做法，讓我們一起欣賞一下吧。

Maximum Flow O(E² * V²)： 適合人數約 30~150

難度略高於 Leetcode Hard

這個做法是從這篇文章看來的，該作者對這個問題研究滿深入，也給出了一個看似可行的做法，但這做法一開始的假設（No one owes a person that they didn’t owe before），就限制了不可能找到最佳步驟數了，我自己實作後也證明某些 case 無法找到最佳解，因此僅能將他當作效率較好的”優化”演算法，他確實在很多情況下能將步驟數大幅化簡，但不保證找到最佳步驟數的答案。

簡單敘述一下他的想法

1. 將原始金錢流向，全部看成有向圖，Vertex 是人，Edge 的權重是給出去的錢
2. 從圖中選出兩人，當成起點與終點，並計算這個起點到終點的 Maximum Flow（不熟 Maximum Flow 概念的人，的可以看這邊的介紹）
3. 找到 Maximum Flow 的值 V 後，將此兩點的 Edge重新改寫為 V，並把原本的圖上對這組 Flow 有貢獻的部分移除掉，剩下的圖稱之為 Residual Graph。
4. 重複步驟 2，不斷換組直到全數輪過，等於把任兩人間的最優結清方式找出來

但實測後，雖然效果不錯，但也有無法找到最優解的 Case 如下：

理論上最優解應該是化簡到 3 步

但 Maximum Flow 找不到這樣的路徑出來，因為 1–>4 這種新路徑，在原本的圖上走不通。

因此如果人數在 30 以內，我們還能有效率的靠前兩個演算法找出最優解，如果超過的話，使用第三種方法，也能找到還不錯的解，大約能支撐到 100 人，且交換關係不要過度複雜時都沒問題，以正常情境來說，可以說完全夠用了。

另外，其實 Splitwise 的做法，由於他的三大假設

1. Everyone owes the same net amount at the end

2. No one owes a person that they didn’t owe before

3. No one owes more money in total than they did before the simplification.

導致無法找到最佳步驟數，但或許反而更貼近人們心目中想要的答案，因此真實世界中，步驟數最少的做法，也未必就是最好的啊！

對這個問題的研究就先到這邊啦，如果有人有完美的 linear time 解法，或能證明無 linear time 解，都歡迎在留言區告訴我。最後補充一下，這題其實 Leetcode 是有的，編號是 465，由於 n 不大，所以前兩個做法都可以 AC，但目前是鎖住的題目，需付費才看得到。