剑指offer 39- 数字排列

先看不包含重复数字的

输入一组数字（不包含重复数字），输出其所有的排列方式。
样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

分析：
回溯的经典题
回溯的思路：

• 先找一个路径出来，记录下来这个路径。
• 擦掉最后一次的查找记录，返回上一层
• 重新找倒数第二层，找到以后继续找下一层，直到找到一个新的路径

• 限定条件：每一层查找出来的数字都必须和其他不同

  
  图片来源于网络

时间复杂度分析：

搜索树中最后一层共 个叶节点，在叶节点处记录方案的计算量是 ，所以叶节点处的计算量是
搜索树一共有
个内部节点，在每个内部节点内均会for循环 n 次，因此内部节点的计算量也是。 所以总时间复杂度是

class Solution {
public:
    vector<vector<int>> res;//结果数组
    vector<bool> st;//状态数组
    vector<int> path;//保存当前路径的数
    vector<vector<int>> permutation(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++) st.push_back(false);
        dfs(nums, 0);
        return res;
    }
    
    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {//u==nums.size()说明当前路径结束，返回一种情况
            res.push_back(path);
            return;
        }
        
        for(int i=0; i<nums.size(); i++) {
            if(!st[i]) {
                st[i] = true;
                path.push_back(nums[i]);
                dfs(nums, u+1);
                //从每个分支退回来的时候需要把修改过的状态还原
                st[i] = false; 
                path.pop_back();
            }
        }
    }
};

再看一题可能包含重复数字的

输入一组数字（可能包含重复数字），输出其所有的排列方式。
样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

分析：
由于有重复元素的存在，这道题的枚举顺序和上次不同。

先将所有数从小到大排序，这样相同的数会排在一起；
从左到右依次枚举每个数，每次将它放在一个空位上；
对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 start，我们在枚举当前数时，只枚举 start+1,start+2,…,n这些位置。
不要忘记递归前和回溯时，对状态进行更新。

时间复杂度：
搜索树中最后一层共 个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是 ，所以总时间复杂度是 。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> st, path;
    vector<vector<int>> permutation(vector<int>& nums) {
        st = vector<int>(nums.size(), false);
        sort(nums.begin(), nums.end());
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return res;
    }
    
    void dfs(vector<int>& nums, int u, int start) {
        if(u == nums.size()) {
            res.push_back(path);
            return;
        }
        if(!u || nums[u] != nums[u-1]) start = 0;
        for(int i=start;i<nums.size();i++) {
            if (!st[i]) {
                st[i] = true;
                path[i] = nums[u];
                dfs(nums, u+1, i+1);
                // 用st[i]表示path[i]是否存在
                // st[i] == false，表示path[i]存在；
                // st[i] == true，表示path[i]不存在；
                // 当st[i] == false时，path[i]下次会被新的值覆盖掉，所以就不需要再remove了。
                st[i] = false;
            }
        }
    }
};

另一种解法：

class Solution {
public:
    vector<vector<int>> res;
    // vector<int> st;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
        // st = vector<int>(nums.size(), false);
        sort(nums.begin(), nums.end());
        // path = vector<int>(nums.size());
        path.resize(nums.size());
        dfs(nums, 0, 0, 0);
        return res;
    }
    
    void dfs(vector<int>& nums, int u, int start, int state) {
        if(u == nums.size()) {
            res.push_back(path);
            return;
        }
        if(!u|| nums[u] != nums[u-1]) start = 0;
        
        for(int i=start;i<nums.size();i++) {
            if(!(state>>i&1)) {
                path[i] = nums[u];
                dfs(nums, u+1, i+1, state+(1<<i));
            }
        }
    }
};