top145-#46

[LionCoder4ever]

dfs, input: [1,2,3]
depth0: []
depth1: [1]
depth2: [1,2], [1,3]
depth3: [1,2,3], [1,3,2]
when depth == length, end the current search;
when come to [1,2,3], try backtrack to [1], release used[2], the loop i come to 2, stack push into the path, [1,3]....

走完第一个循环[1,2,3]后，弹出3，弹出2，把标记3，2 使用过的used数组还原成false, 继续走for循环，used[2]为false，压入栈中得[1,3]
再进行深度遍历，depth=3...

class Solution {
public:
    void dfs(vector<int>& nums,int n, int depth, stack<int> path,bool used[], vector<vector<int>>& res){
        if (depth == n) {
            vector<int> ans(0);
            for(int i=0;i<n;i++) {
                ans.push_back(path.top());
                path.pop();
            }
            res.push_back(ans);
            return ;
        }
        for(int i=0;i<n;i++) {
            if(used[i]) {
                continue;
            }
            path.push(nums[i]);
            used[i] = true;
            dfs(nums,n,depth+1, path,used, res);
            path.pop();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        // pro--    n * n-1 * n-2 * 1
        // 6 * 5 * 4 * 3 * 2 * 1
        // 1 2 3
        // 1 2 3
        // 1 2 3
        int n = nums.size();
        vector<vector<int>> res(0);
        stack<int> path;
        bool used[n];
        for(int i =0;i<n;i++) {
            used[i] = false;
        }
        dfs(nums, n, 0, path,used, res);
        return res;
    }
};