某连锁店开设了若干门店，门店间允许进行商品借调以应对暂时性的短缺。本月商品借调的情况记于数组 distributions，其中 distributions[i] = [from,to,num]，表示从 from 门店调配了 num 件商品给 to 门店。
若要使得每一个门店最终借出和借入的商品数量相同，请问至少还需要进行多少次商品调配。
注意：一次商品调配以三元组 [from, to, num] 表示，并有 from ≠ to 且 num > 0。
示例 1：
输入：distributions = [[0,1,5],[1,2,10],[2,0,5],[2,1,1]] 输出：1 解释： 商店 0 给商店 1 五件商品； 商店 1 给商店 2 十件商品； 商店 2 给商店 0 五件商品； 商店 2 给商店 1 一件商品。 此时商店 1 少了 4 件商品，商店 2 多了 4 件商品， 因此仅需一次商品调配，商店 2 给商店 1 四件商品，即可满足每个门店借出和借入商品数量相同： 商店 0 借出和借入的商品数量均为 5； 商店 1 借出和借入的商品数量均为 10； 商店 2 借出和借入的商品数量均为 10。
示例 2：
输入：distributions = [[0,1,5],[1,4,5],[4,0,5]] 输出：0 解释： 此时各商店借入和借出的商品数量均相等，无需额外的商品调配。
方法一：回溯
思路：
1.先转成map ，门店号—>商品数量 （借入的为+，借出的为-）
2.将map转成vector数组，数组存放的是每个门店的商品数量
3.回溯
回溯思路：
每个门店的当前商品数量cur如果不是0的话，必定要和一个商店交换，因此通过回溯遍历，找到另外一个交换的门店的商品数量next
交换的规则：比如 cur=-5 ，next=4，回把cur所有的商品数量都给next，更新后cur=-5，next=-1
为什么cur不设置0呢？其实是可以的，只是没必要，后续遍历都是cur+1开始，根本访问不到之前的cur，因此cur不需要设置0。
数量为0的门店一定要跳过：
比如[-4,4,0,0],如果cur=2，
- 假如跳过，那么cur=4，直接可以更新结果res
- 假如不跳过，那么cur=2，不会更新结果，继续往下走，
counts[next]*counts[cur]=0永远是0，后续也不会更新res了。
class Solution { private: vector<int> counts; int res=INT_MAX; void dfs(int cur,int times){//cur为当前需要调配的一个门店的商品数 if(times>=res) return; while(cur<counts.size()&&counts[cur]==0) cur++;//数量为0的门店直接跳过 if(cur==counts.size()){ res=min(res,times); return; } for(int next=cur+1;next<counts.size();next++){//遍历，寻找与cur交换的门店next if(counts[next]*counts[cur]<0){ counts[next]+=counts[cur]; dfs(cur+1,times+1); counts[next]-=counts[cur]; } } } public: int minTransfers(vector<vector<int>>& distributions) { //map:门店->商品数量 unordered_map<int,int> mp; for(vector<int>& dist:distributions){ mp[dist[0]]-=dist[2]; mp[dist[1]]+=dist[2]; } //map转成vector for(auto it=mp.begin();it!=mp.end();it++){ counts.push_back(it->second); } //回溯 dfs(0,0); return res; } };
