【LeetCode热题100】【回溯】全排列

题目链接：46. 全排列 - 力扣（LeetCode）

要找出所有数字的全排列，可以用深度优先遍历，用一个访问数组记录当前数字有没有被访问，在没有被访问的数字中继续深搜下去，回来的时候恢复状态，即回溯

class Solution {
public:
    vector<bool> visited;
    vector<vector<int> > ans;
 
    void dfs(vector<int> &array, vector<int> &nums) {
        if (array.size() == nums.size()) {
            ans.push_back(array);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (visited[i] == false) {
                visited[i] = true;
                array.push_back(nums[i]);
                dfs(array, nums);
                array.pop_back();
                visited[i] = false;
            }
        }
    }
 
    vector<vector<int> > permute(vector<int> &nums) {
        visited.assign(nums.size(), false);
        vector<int> array;
        dfs(array, nums);
        return ans;
    }
};