力扣每日一题 -【全排列】

题目链接
视频讲解

class Solution {
public:
    vector<vector<int>> res; 
    vector<int> path;   
    vector<bool> st; //path数组中元素的映射位

    vector<vector<int>> permute(vector<int>& nums) {
        st.resize(nums.size(), false);
        path.resize(nums.size());
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int> &nums, int u)
    {
        if(u >= nums.size()){ //记录总方案数
            res.push_back(path);  
            return ;
        } 

        for(int i = 0; i < nums.size(); i++){
            if(!st[i]){
                path[u] = nums[i];
                st[i] = true;    //选完当前层的数后， 将标志位改成true
                dfs(nums, u + 1);  //选下一层的数
                st[i] = false;     //回溯， 将标志位改成false， 方便清空path的值
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30