天池 在线编程 订单分配（回溯）

样例 1
输入：
[[1,2,4],[7,11,16],[37,29,22]]
输出：
[1,2,0]
解释：
标号为0的订单给标号为1的司机，获得 score[0][1] = 2 分，
标号为1的订单给标号为2的司机，获得 score[1][2] = 16 分，
标号为2的订单给标号为0的司机，获得 score[2][0] = 37 分，
所以一共获得了 2 + 16 + 37 = 55 分。

class Solution {
public:
    /**
     * @param score: When the j-th driver gets the i-th order, we can get score[i][j] points.
     * @return: return an array that means the array[i]-th driver gets the i-th order.
     */
	int ans = 0;//最大总和
	vector<int> path;//选取的最佳方案
    vector<int> orderAllocation(vector<vector<int>> &score) {
        // write your code here
        int n = score.size();
        vector<bool> vis(n, false);
        vector<int> p(n);
        dfs(score, vis, 0, 0, p);
        return path;
    }
    void dfs(vector<vector<int>> &score, vector<bool>& vis, int i, int val, vector<int>& p)
    {
    	if(i == score.size())
    	{
    		if(val > ans)
    		{
    			ans = val;
    			path = p;
    		}
    		return;
    	}
    	for(int j = 0; j < score.size(); ++j)
    	{
    		if(vis[j]) continue;//物品 j 被选了
    		vis[j] = true;
    		p[i] = j; // 选取的方案 ， i 选取了 j 物品
    		dfs(score, vis, i+1, val+score[i][j], p);
    		vis[j] = false;
    	}
    }
};