题解 | #牛群排队#

考察知识点：回溯

回溯法的定义（来源：制心一处）

回溯法（back tracking）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回到上一步，重新选择。

题目分析：

因为题目要求降序返回答案，所以我们先对nums进行排序，然后按照数组中数的顺序来进行递归回溯。这样数大的在前面并先被选择，就是我们的优选条件。

回溯法就是这样试探性地进行选择，当满足条件时就加入到结果中；否则就回溯回去，试探性选择下一个优选值。注意回溯时要恢复现场，消除由于上一次的选择所产生的影响。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    void dfs (vector<int> &nums, vector<int> &cows, vector<vector<int>> &res, vector<bool> st) {
        int size = nums.size();
        if (cows.size() == size) {
            res.push_back(cows);
            return;
        }

        for (int i = 0; i < size; i++) {
            if (st[i]) continue;
            cows.push_back(nums[i]);
            st[i] = true;
            dfs(nums, cows, res, st);
            st[i] = false;
            cows.pop_back();
        }
    }
    vector<vector<int> > cow_permute(vector<int>& nums) {
        // write code here
        sort(nums.begin(), nums.end(), greater<int>());
        vector<vector<int>> res;
        vector<int> cows;
        vector<bool> st(nums.size(), false);	//记录nums[i]是否被访问过
        dfs(nums, cows, res, st);
        return res;
    }
};