NP Complete Problems
You are given an array of transactions
transactions[i] = [fromi, toi, amounti] indicates that the person with
ID = fromi gave
amounti $ to the person with
ID = toi.
Return the minimum number of transactions required to settle the debt.
The question below is similar to an N way partition problem (instead of 3 way partition problem
Then the problem can be converted to the following:
Given N accounts/persons who have non zero amounts,
find the M = max number of sets where each set s has sum(s)==0.
Each of these sets must be min_set. In other words, min_set CANNOT be divided to setA and setB where sum(setA) == sum(setB)==0.