以全排列问题为例，DFS的背景通常可以抽象成“做选择”

• DFS的核心思想是，一条路走到头，在每一个岔路口“做选择”，同时记录“已经作出的选择”，以便在下个路口知晓“可以做哪些选择”，最终记录“这条路的选择情况”

• 通常需要这些固定的变量

  • 一个vector<vector>res 来存储输出的结果

  • 一个vector path 存储已作出的选择

  • 一个vectorvisited(n) 当前位置可做的选择

  • 结束递归的标志通常是 path.size() == num.size() 即当前节点已经昨晚了一套完整的选择

• tips：

  • 每个节点，代表的是当前层的path（即第n层节点代表已经作出的n个选择）
  • 每条边，代表的是下一层作出的选择，我们需要将边加入path
  • 通常从第0层，空集合 开始考虑
  • 比如从第0层开始，一共有3条边可以走（1,2,3），那么当前递归方法首部是对当前第0层节点进行处理，递归法方法尾部是对3条边分别进行处理，即for(int i = 1 ; i <=3 ; i ++)，在每个i下，分别通过visited[i]==true 来判断是否可以path.push_back(i)，即将边加入path，然后进入第1层。等第1层处理完后，再通过visited[i]=false和path.pop_back()撤销当前第1层作出的选择，再退回到第0层，以此类推。

class Solution {
public:

    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        int n = nums.size();
        vector<bool>visited(n);
        backtrack(nums,visited,path);
        return res;
    }

    void backtrack(vector<int>& nums,vector<bool>& visited,vector<int>& path){

        // base case
        if(path.size() == nums.size()){
            res.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++){
            if(visited[i])
                continue;
            path.push_back(nums[i]);
            visited[i] = true;
            backtrack(nums,visited,path);
            visited[i] = false;
            path.pop_back();
        }
    }
};

更好理解的版本

• 通过变量k感受递归的层数变化

class Solution {
public:

    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        int n = nums.size();
        vector<bool>visited(n);
        backtrack(nums,visited,path,0);
        return res;
    }

    void backtrack(vector<int>& nums,vector<bool>& visited,vector<int>& path,int k){

        // base case
        if(k == nums.size()){
            res.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++){
            if(visited[i])
                continue;
            path.push_back(nums[i]);
            visited[i] = true;
            backtrack(nums,visited,path,k+1);
            visited[i] = false;
            path.pop_back();
        }
    }
};