递归/回溯刷题(上)

一、没有重复项数字的全排列

解法一:递归+回溯(推荐)

• 例如[1,2,3,4],如果遍历经过元素2后，前半部分1和2的位置就不变了，对3，4进行排序，后半部分就相当于一个全排列，即为子问题
• 当到数组末尾时终止
• 使用递归的同时还要使用回溯，返回开始进行不同分支选择

public:
    void fun(vector<vector<int>>&tmp,vector<int>&num,int index)
    {
    
        int n=num.size();
        if(index==n-1)//分支进入结尾找到一种排列
            tmp.push_back(num);
        else
        {
    
            for(int i=index;i<n;i++)
            {
    
                swap(num[i],num[index]);//交换
                fun(tmp,num,index+1);//继续往后查找
                swap(num[i],num[index]);//回溯
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
    
        sort(num.begin(),num.end());//升序排
        vector<vector<int>>tmp;
        fun(tmp,num,0);//地柜获取
        return tmp;
    }
};

时间复杂度：O(n∗n!)，近似O(n^2)，n个元素的数组进行全排列的递归，每次递归都要遍历数组
空间复杂度：O(n)，递归栈的最大深度为数组长度n，tmp属于返回必要空间

解法二:库函数

使用next_permutation进行全排列

class Solution {
    
public:
    vector<vector<int> > permute(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<vector<int>>v;
        do{
    
            v.push_back(num);
        }while(next_permutation(num.begin(), num.end()));//库函数
        return v;
    }
};

时间复杂度：O(n!)，n个元素的数组进行全排列
空间复杂度：O(1)，返回矩阵v属于必要空间，不属于额外空间

二、有重复项数字的全排列

解法一:递归+回溯(推荐)

• 先对数组按照字典序排序
• 准备一个数组暂存递归过程中组装的排列情况。使用额外的back数组用于记录哪些位置的数字被加入了。
• 每次递归从头遍历数组，获取数字加入：首先根据back数组，已经加入的元素不能再次加入了；同时，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用，也不需要将其纳入。
• 进入下一层递归前将back数组当前位置标记为使用过。
• 回溯的时候需要修改back数组当前位置标记，同时去掉刚刚加入数组的元素，
• 临时数组长度到达原数组长度就是一种排列情况。

class Solution {
    
public:
    void fun(vector<vector<int>>&res,vector<int>&num,vector<int>&tmp,vector<int>back)
    {
    
        if(tmp.size()==num.size())//临时数组满了加入输出
        {
    
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<num.size();i++)
        {
    
            if(back[i])//如果该元素已被加入，无需再入
                continue;
            if(i>0&&num[i-1]==num[i]&&!back[i-1])//num[i]和num[i-1]已经用过
                continue;
            back[i]=1;//标记为使用过
            tmp.push_back(num[i]);
            fun(res,num,tmp,back);
            back[i]=0;//回溯
            tmp.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<int>back(num.size(),0),//初始化未被使用过
        tmp;
        vector<vector<int>>res;
        fun(res,num,tmp,back);
        return res;
    }
};

时间复杂度：O(n∗n!)，全排列的全部情况为n!，每次递归过程都是遍历数组查找元素，这里是O(n)
空间复杂度：O(n)，递归栈的最大深度为数组长度n，临时数组temp的空间也为O(n)，res属于返回必要空间

解法二:库函数

class Solution {
    
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<vector<int>>res;
        do{
    
            res.push_back(num);
        }while(next_permutation(num.begin(), num.end()));
        return res;
    }
};

和第一题一样使用
时间复杂度：O(n!)，n个元素的数组进行全排列
空间复杂度：O(1)，返回矩阵res属于必要空间，不属于额外空间

三、自己实现next_permutation

class Solution {
    
public:
    bool mynext_Permutation(vector<int> &num) {
    
    int i = num.size() - 2;
    while (i >= 0 && num[i] >= num[i + 1]) {
    
        i--;
    }
    if (i < 0) {
    
        return false;
    }
    int j = num.size() - 1;
    while (j >= 0 && num[i] >= num[j]) {
    
        j--;
    }
    swap(num[i], num[j]);
    reverse(num.begin() + i + 1, num.end());
    return true;
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<vector<int>>res;
        do{
    
            res.push_back(num);
        }while(mynext_Permutation(num));
        return res;
    }
};

时间复杂度：O(n!)，n个元素的数组进行全排列
空间复杂度：O(1)，返回矩阵res属于必要空间，不属于额外空间