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

491.递增子序列

代码随想录链接

题目

LeetCode-491.递增子序列

给定一个数字序列, 返回所有递增的子序列, 每个子序列里至少有两个元素.

自己的想法

递增的子序列, 需要注意的点是这是个序列, 子序列中元素的相对位置是要保持和原序列中相对位置的.

针对于子序列中元素的相对顺序不变, 需要在回溯函数的参数中加入startIndex来标定纵向递归左侧的起始位置.

横向的for循环需要注意两个条件: * 新加入的数据必须要大于当前序列末尾的数据 * 当前位置已经出现过的元素不可以再次出现

递归的结束条件是标定的起始位置startIndex抵达了数组的边界.

当目前子序列中有两个及以上元素时, 需要将当前子序列保存到结果当中.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> current;
    void backtracing(vector<int> &nums, int startIndex) {
        if (current.size() >= 2) result.push_back(current);         // 当前子序列长度大于2时, 保存该序列
        if (startIndex >= nums.size()) return;                      // 超越了边界, 则结束递归

        unordered_set<int> set;                                     // 当前位置的元素去重
        for (int i = startIndex; i < nums.size(); i++) {
            if ((current.empty() || current.back() <= nums[i]) && set.find(nums[i]) == set.end()) { // 当当前位置的元素大于子序列末尾元素且不重复出现时, 进行纵向递归
                set.insert(nums[i]);
                current.push_back(nums[i]);
                backtracing(nums, i + 1);
                current.pop_back();
            }
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracing(nums, 0);
        return result;
    }
};

46.全排列

代码随想录链接

题目

LeetCode-46.全排列

给定一个不含重复数字的数组, 返回其全部的全排列.

自己的想法

要求比较少, 不含重复数字的话其实就是$ P_n^n $ 个结果.

使用一个used数组来标记当前元素是否已经使用, 横向for循环决定当前位置是哪个元素, 纵向递归处理下一位置的元素.

由于是全排列, 所以for循环的起始点每次都应该是数组左侧开始.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> current;
    void backtracing(vector<int> &nums, vector<bool> &used) {
        if (current.size() == nums.size()) {        // 如果当前数组长度已经和原数组长度相同, 证明所有元素都已加入, 需要记录结果
            result.push_back(current);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {     // 横向决定当前位置是哪个元素
            if (!used[i]) {         // 元素没有使用过时才进行递归
                current.push_back(nums[i]);
                used[i] = true;
                backtracing(nums, used);
                current.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtracing(nums, used);
        return result;
    }
};

47.全排列 II

代码随想录链接

题目

LeetCode-47.全排列 II

给定可能包含重复数字的序列, 返回不重复的全排列.

自己的想法

就是上面两道题简单缝合了一下. 需要使用一个bool数组来标记哪些位置的数据已经加入了组合, 又需要保证当前位置不重复出现同一个数.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> current;
    void backtracing(vector<int> &nums, vector<bool> &used) {
        if (current.size() == nums.size()) {    // current数组大小等于原数组大小, 证明所有元素均已加入, 将结果保存
            result.push_back(current);
            return;
        }

        unordered_set<int> set; // 用来确保当前位置没有重复的数据出现
        for (int i = 0; i < nums.size(); i++) {
            if (set.find(nums[i]) != set.end() || used[i]) continue;    // 如果for循环到的元素没有出现过, 且也没有在组合里, 就进行纵向递归.
            set.insert(nums[i]);    // 标记出现过的元素
            current.push_back(nums[i]);
            used[i] = true;
            backtracing(nums, used);
            current.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtracing(nums, used);
        return result;
    }
};