LeetCode 46.全排列

题目描述链接：https://leetcode-cn.com/problems/permutations/

解题思路：DFS加回溯。对于给出的序列分别出不同的起点进行DFS搜索并回溯以找到全部答案。

LeetCode C++求解参考代码如下：

class Solution {
public:

    bool vis[10];
    vector<int>ans;
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
              dfs(nums,i);
        return res;
    }

    void dfs(vector<int>&nums,int x){
          
          if(x==nums.size()){//&&ans.size()==nums.size()){//found
            if(ans.size()==nums.size())//由于x==nums.size没有vis数组维护访问，所以可能
            //存在x==nums.size()但没有全部遍历的情况，所以需判断一下长度
                res.push_back(ans);
            return;
          }
          vis[x]=1;
          ans.push_back(nums[x]);
          for(int j=0;j<=nums.size();j++){
              if(vis[j]!=1){//不存在
                 dfs(nums,j);
              }
          }
          vis[x]=0;
          ans.pop_back();
    }

};