If someone gives me $10 and I give that person $10 back, it would mean that there are 0 transactions needed.
If I give that person only $8 back, the situation is equivalent to me getting only $2 from the person.
If someone comes and gives the person in $2 deficit that money, the situation is now equivalent to the new person giving me $2. So, we calculate how much each person is in deficit/surplus. If their accounts are balanced with $0 change, we don't include them in the debts list, as no transactions will be done with them.
Some debts will directly cancel each other. In the state above, the debts would look like this: [-2, 2] (second person is balanced). These values would directly cancel each other, so we don't need extra computation for it. But what if the debts look like this: [-4, -4, 2, 6]. We can try paying the first person with the 3. Then we have [0, -4, -2, 6]. We can pay the second with the last to get [0, 0, -2, 2]. The last two can cancel each other out and we would be left with 3 transactions. This is in fact the solution here, but it may not be in other situations. So, we might have to try all opposite-signed balances. For this, to cancel out the side-effects of the previous trial, we can use simple backtracking.
Resolves: #224
Algorithm:
If someone gives me $10 and I give that person $10 back, it would mean that there are 0 transactions needed. If I give that person only $8 back, the situation is equivalent to me getting only $2 from the person. If someone comes and gives the person in $2 deficit that money, the situation is now equivalent to the new person giving me $2. So, we calculate how much each person is in deficit/surplus. If their accounts are balanced with $0 change, we don't include them in the debts list, as no transactions will be done with them. Some debts will directly cancel each other. In the state above, the debts would look like this:
[-2, 2](second person is balanced). These values would directly cancel each other, so we don't need extra computation for it. But what if the debts look like this:[-4, -4, 2, 6]. We can try paying the first person with the 3. Then we have [0, -4, -2, 6]. We can pay the second with the last to get [0, 0, -2, 2]. The last two can cancel each other out and we would be left with 3 transactions. This is in fact the solution here, but it may not be in other situations. So, we might have to try all opposite-signed balances. For this, to cancel out the side-effects of the previous trial, we can use simple backtracking.