题解 | #没有重复项数字的全排列# 回溯/DFS

官网代码会导致排列顺序有错，仅适用于组合；如果仅仅只是交换两个值的位置，不能保证排序；

本文采用的方法，每次从头开始遍历各个元素，保证当前未被遍历过的最小的元素排在最前面。

使用一个foot数组记录遍历过的位置。

另外：附上一个奇奇怪怪的快排

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        quick_sort(num, 0, num.size() - 1);
        vector<bool> foot(num.size(), false);
        vector<vector<int>> res;
        vector<int> arr;
        dfs(res, num, arr, foot, 0);
        return res;
    }

    void dfs(vector<vector<int>> &res, vector<int> &num, vector<int> &arr,vector<bool> &foot, int depth) {
        if (depth == num.size()) {
            res.emplace_back(arr);
            return ;
        }
        for (int i = 0; i < num.size(); ++i) {
            if (foot[i]) continue;
            arr.emplace_back(num[i]);
            foot[i] = true;
            dfs(res, num, arr, foot, depth + 1);
            arr.pop_back();
            foot[i] = false;
        }
    }

    void quick_sort(vector<int> &num, int l, int r) {
        if (l >= r) return;
        int i = l - 1, j = r + 1;
        int mid_v = num[(i + j) >> 1];
        while (i < j) {
            do ++i; while (num[i] < mid_v);
            do --j; while (num[j] > mid_v);
            if (i < j) swap(num[i], num[j]);
        }
        quick_sort(num, l, j);
        quick_sort(num, j + 1, r);
    }
};