465. Optimal Account Balancing

实现splitwise的核心算法，一堆借钱的transaction，问最少需要安排几次还账能让所有人清账。先重新组织数据，把每个人的balance建成一个map。DFS遍历所有可能的还款方式，找出最短让所有balance清0的方式，用排序来跳过效果相同的还款方式作为小优化。还有DP解法是把所有人看成由两个subgrounp拼成的，用二进制encoding所有可能的combination，检查每个subgroup的balance和是否为0，为0意味着该group收支平衡。

class Solution {
public:
    /*
     * @param edges: a directed graph where each edge is represented by a tuple
     * @return: the number of edges
     */
    int dfs(vector<int> &debt, int cur, int count) {
        const int N = debt.size();
        while (cur < N && debt[cur] == 0) ++cur;
        if (cur == N) return count; 
        int res = N;
        for (int i = cur + 1; i < N; ++i) {
            if ((i > cur + 1 && debt[i] == debt[i - 1]) || (debt[i] * debt[cur] > 0)) continue;
            debt[i] += debt[cur];
            res = min(res, dfs(debt, cur + 1, count + 1));
            debt[i] -= debt[cur];
        }
        return res;
    }
    int balanceGraph(vector<vector<int>> &edges) {
        unordered_map<int, int> m;
        for (const auto &e : edges) {
            m[e[0]] -= e[2];
            m[e[1]] += e[2];
        }
        vector<int> debt;
        for (const auto &p : m) {
            if (p.second != 0) debt.push_back(p.second);
        }
        sort(debt.begin(), debt.end());
        return dfs(debt, 0, 0);
    }
    
};