代码随想录算法训练营第二十九天| 491.递增子序列 46.全排列 47.全排列 II

491.递增子序列

题目链接：491. 非递减子序列 - 力扣（LeetCode）

思路：一开始一直报访问异常的错误，最后只好参考官网答案，结果竟然是因为我递归参数写错了导致程序一直出问题？？？(⊙︿⊙)

这里去重用的是标记数组，可以用集合unordered_set，但由于本题数据范围比较小，所以我们可以用数组更加高效的解决。

class Solution {
public:
    vector<vector<int>>result;
    vector<int>path;
    void backtracking(vector<int> nums,int start){
        if(path.size()>1){
            result.push_back(path);
        }
        int use[201]={0};
        for(int i=start;i<nums.size();i++){
            if((!path.empty()&&path.back()>nums[i])
                    ||use[nums[i]+100]==1){
                continue;
            }
                use[nums[i]+100]=1;
               path.push_back(nums[i]);
               backtracking(nums,i+1);
               path.pop_back();
            
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

46.全排列

题目链接：46. 全排列 - 力扣（LeetCode）

思路：利用了上一题中学到的标记数组法，用长度为6的数组记录该元素是否被使用过。注意不要在result保存结果后将数组清零，证明对回溯法理解不到位。

class Solution {
public:
    vector<vector<int>>result;
    vector<int>path;
    int count[6]={0};
    void backtracking(vector<int> nums){
        if(path.size()==nums.size()){
            result.push_back(path);
//            memset(count,0,sizeof(count));
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(count[i]){
                continue;
            }
            path.push_back(nums[i]);
            count[i]=1;
            backtracking(nums);
            count[i]=0;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums);
        return result;
    }
};

观察题解区发现还有一种不用标记数组而是利用交换的方法。

举个简单的例子，假设我们有 [2,5,8,9,10][2, 5, 8, 9, 10][2,5,8,9,10] 这 555 个数要填入，已经填到第 333 个位置，已经填了 [8,9][8, 9][8,9] 两个数，那么这个数组目前为 [8,9 ∣ 2,5,10][8, 9~|~2, 5, 10][8,9 ∣ 2,5,10] 这样的状态，分隔符区分了左右两个部分。假设这个位置我们要填 101010 这个数，为了维护数组，我们将 222 和 101010 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8,9,10 ∣ 2,5][8, 9, 10~|~2, 5][8,9,10 ∣ 2,5] 。

当然善于思考的读者肯定已经发现这样生成的全排列并不是按字典序存储在答案数组中的，如果题目要求按字典序输出，那么请还是用标记数组或者其他方法。

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/permutations/solutions/218275/quan-pai-lie-by-leetcode-solution-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

47.全排列 II

题目链接：47. 全排列 II - 力扣（LeetCode）

思路：注意本题的去重方式，count[i-1]==0，该句的运作原理可以参照下图。其他与上一题一致。

class Solution {
public:
    vector<vector<int>>result;
    vector<int>path;
    int count[8]={0};
    void backtracking(vector<int> nums,int count[]){
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(i&&nums[i]==nums[i-1]&&count[i-1]==0){
                continue;
            }
            if(count[i]==0){
                count[i]=1;
                path.push_back(nums[i]);
                backtracking(nums,count);
                path.pop_back();
                count[i]=0;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums){
        sort(nums.begin(),nums.end());
        backtracking(nums,count);
        return result;
    }
};