L465. Optimal Account Balancing

First we need to count the net balance for every person, we define it as the list "net".
The question is the same as finding the "loop" in a graph
 (which the sum of elements in each graph is 0), say, the answer is len(net) - number of circles.
Thus, in order to minimize the answer, 
we need to maximize the number of circle, so we need to let every circle become "smaller",
 which is the same as "shortest path in a circle", we can use BFS to solve it.

#从任一点开始，用BFS找最小能形成的circle
import Queue
from collections import defaultdict
class Solution(object):
    def minTransfers(self, transactions):
        """
        :type transactions: List[List[int]]
        :rtype: int
        """
        def bfs(net):
            while q:
                t, path, start = q.pop()
                if t==0: # 如果当前cycle netincome 是0， circle形成，跳出while 
                    break
                for i in xrange(start, len(net)):
                    q.append((t+net[i], path+[i], i+1))

            self.res += len(path)-1 # length -1 是当前cycle需要的transcation
            path = set(path)
            return [net[i] for i in xrange(len(net)) if i not in path] #把cycle里的node去掉，继续下一轮bfs

        d = defaultdict(int) #net income
        for t in transactions:
            d[t[0]] -= t[2] #第一个人付了这么多钱
            d[t[1]] += t[2] #被付款的需要付这么多
        net = [d[item] for item in d if d[item] != 0] # net income 

        self.res = 0
        while len(net): #当还有没付清的继续找
            q = []
            q.append((net[0], [0], 1)) #income(weight), path, start index
            net = bfs(net)
        return self.res

[Original post]
First step is quite clear. We need to exclude those people who ends up not owing or owed money.

Then we will have an array of non-zero numbers, which sums to be zero. For example

[4, -2, -2, 6, -6]

This can be converted into finding the minimal clique such that the 
elements sum up to be zero. Minimal means there is no subset which sums up to zero.
 In the example above, there are two minimal such cliques.

[4, -2, -2] and [6, -6]

The beautiful part of those cliques are that we only need to resolve the balance inside the clique.
 There will be no inter-clique transactions.

The final number of transactions will be 5 - 2, which is num_non_zero - num_clique.

To find the minimal clique is the perfect problem to be solved by BFS.
 We will start with one element in the set as the root, find the minimal length
  path in the tree which sum up to be zero. Remove that zero sum set and pick another root.


class Solution(object):
    def minTransfers(self, transactions):
        """
        :type transactions: List[List[int]]
        :rtype: int
        """
        def remove_one_zero_clique(non_zero):
            n = len(non_zero)
            q = collections.deque()            
            # q store ([index set], sum of set)
            q.append(([0], non_zero[0]))
            min_zero_set = None

            while q:
                cur_set, cur_sum = q.popleft()
                if cur_sum == 0:
                    min_zero_set = cur_set
                    break
                for j in range(cur_set[-1] + 1, n):
                    q.append((cur_set + [j], cur_sum + non_zero[j]))

            min_zero_set = set(min_zero_set)
            return [non_zero[i] for i in range(n) if i not in min_zero_set]


        bal = collections.defaultdict(int)
        for t in transactions:
            bal[t[0]] -= t[2]
            bal[t[1]] += t[2]
        non_zero = [bal[k] for k in bal if bal[k] != 0]

        bal_cnt = len(non_zero)
        while len(non_zero) > 0:
            non_zero = remove_one_zero_clique(non_zero)
            bal_cnt -= 1
        return bal_cnt