算法训练营第三十一天 | LeetCode 491非递减子序列、LeetCode 46 全排列、LeetCode 47 全排列II

LeetCode 491 非递减子序列

这题对于之前一直套模板的我来说算是狠狠的一个打击了。去重之前不能进行排序。所以每一层要用一个哈希表或者数组进行去重记录。这题数值的范围较小，就使用数组了。每次记录完后不用再像path一样修改回来。因为这一层就需要一直保持着这种记录的状态。到了下一层的话是另一个函数，当前栈空间内记录的数组不会对下一层数组造成影响。代码如下：

class Solution {
private:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int>& nums, int index, int size) {
        if (path.size() == size) {
            res.push_back(path);
            return;
        }
        if (index == nums.size()) return;
        vector<int> used(201, 0);
        for (int i = index; i < nums.size(); i++) {
            if (used[nums[i] + 100] == 1) continue;
            if (path.size() == 0 || nums[i] >= path[path.size() - 1]) {
                path.push_back(nums[i]);
                used[nums[i] + 100] = 1;
                backtracking(nums, i + 1, size);
                path.pop_back();
            }
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // sort(nums.begin(), nums.end());
        for (int i = 2; i <= nums.size(); i++)
            backtracking(nums, 0, i);
        return res;
    }
};

LeetCode 46 全排列

这一题有了上一道题的基础就比较简单了。我们不用再用一个index来限定每一层起始节点，取而代之的是，我们需要用一个全局的used数组像path那样记录每一个元素是否被使用过。并在回溯返回后清楚记录。这样在该逻辑的下一层，我们会知道该元素已经被使用过了。

代码如下：

class Solution {
private:
    vector<int> path;
    vector<int> used = vector<int>(21, 0);
    vector<vector<int>> res;
    void backtracking(vector<int>& nums) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[nums[i] + 10] == 1) continue;
            path.push_back(nums[i]);
            used[nums[i] + 10] = 1;
            backtracking(nums);
            used[nums[i] + 10] = 0;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums);
        return res;
    }
};

LeetCode 47 全排列II

这题采用的是全局下标去重和提前排序+局部循环去重的方式来完成。代码如下：

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