题解 | #没有重复项数字的所有排列#

题解一：回溯
题解思路： 每次尝试选一个数，不满足条件就回溯
图示：

 约束条件：数组不能重复使用.
 递归分析： cur==num.size 表示找到一个全排列
 递归过程： 如果该数字能添加，那么将vis置位1 ，表示该数字已经用了。
  回溯： 恢复状态
复杂度分析:
 时间复杂度： : 共有n！个叶节点，需要使用O(N)的时间复制到目标数组
 空间复杂度： ：排列个数N！，每个排列占N
实现如下：

class Solution {
public:
    int vis[1001];
    vector<vector<int> >ans;
    void dfs(vector<int>& num,int cur,vector<int>&Permutation){
        if(cur==num.size()) {ans.emplace_back(Permutation);return;} //生成了一个排列
        for(int i = 0;i<num.size();i++){
            if(vis[i]!=1){  //没有使用过
                vis[i] = 1;
               Permutation.emplace_back(num[i]);
                dfs(num,cur+1,Permutation);
                //回溯
                vis[i] = 0;
               Permutation.pop_back();  
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        vector<int> Permutation;
        dfs(num, 0,Permutation);
        return ans;
    }
};

题解二：位运算
题解思路：使用二进制位代替了标记数组
比如： 0001表示第一位使用了 0010 表示第二位使用了,0011表示第一位和第二位已经使用了。由于本题的数据弱，一个int数据可以标记完所有数，所以可以使用本方法。或者改用long long。
复杂度分析：
 时间复杂度：,同方法一
 空间复杂度：，同方法一
实现如下：

class Solution {
public:
    vector<int> tmp;
    vector<vector<int> >ans;
    vector<vector<int> > permute(vector<int> &num) {
      int len = num.size();
      Permutation(num,len,0);
      return ans;
    }
    void Permutation(vector<int>& num,int len,int vis){
        for(int i = 0;i<len;++i){
            int cur = 1<<i; //标识当前使用的第几位数
            if((cur&vis)==0){
                tmp.push_back(num[i]);
                Permutation(num,len,vis|cur); 
            }
        }
        if(tmp.size()==len) ans.push_back(tmp);
        tmp.pop_back(); // 回溯
        return;
    }
};