Leedcode刷题 | Day25_回溯算法04
一、学习使命[*]491.递增子序列代码随想录
[*]46.全分列
[*]47.全分列 II
二、具体题目
1.491非递减子序列491. 非递减子序列 - 力扣（LeetCode）
给定一个整型数组, 你的使命是找到全部该数组的递增子序列，递增子序列的长度至少是2。
示例:
[*]输入:
[*]输出: [, , , , , , , ]
说明:
[*]给定数组的长度不会超过15。
[*]数组中的整数范围是 [-100,100]。
[*]给定数组中可能包含重复数字，相等的数字应该被视为递增的一种环境。
[*]不可以排序！！！！！！！因为要求的是子序列，不是子集。
[*]还是树层剪枝的思想，只不外因为不能排序所以不能使用之前的used数组去判定相邻元素是否相同，改为使用unordered_set大概used巨细的数组记载是否重复（因为一共有200个数字）。
[*]所以正如在哈希表：总结篇！（每逢总结必经典） (opens new window)中说的那样，数组，set，map都可以做哈希表，而且数组干的活，map和set都醒目，但假如数值范围小的话能用数组尽量用数组。
unordered_set映射版本：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
// 注意这里不要加return，要取树上的节点
}
unordered_set<int> uset; // 使用set对本层元素进行去重（每次递归/每层有一个新的set）
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums < path.back())
|| uset.find(nums) != uset.end()) {
continue;
}
uset.insert(nums); // 记录这个元素在本层用过了，本层后面不能再用了
path.push_back(nums);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};
数组映射版本：（更快）
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
}
int used = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
// 每次递归/每层一个数组，互不干扰，只记录本层重复情况
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums < path.back())
|| used + 100] == 1) {
continue;
}
used + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了
path.push_back(nums);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
}; 2.46全分列46. 全分列 - 力扣（LeetCode）
给定一个 没有重复 数字的序列，返回其全部可能的全分列。
示例:
[*]输入:
[*]输出: [ , , , , , ]
与组合问题的区别：
[*]每层都是从0开始搜索而不是startIndex
[*]需要used数组记载path里都放了哪些元素了
本题：nums中无重复元素
树枝去重，true就continue；数层去重，false就continue！！！！！！
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used == true) continue; // path里已经收录的元素，直接跳过
used = true;
path.push_back(nums);
backtracking(nums, used);
path.pop_back();
used = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
}; 3.47全分列 II47. 全分列 II - 力扣（LeetCode）
给定一个可包含重复数字的序列 nums ，按恣意次序 返回全部不重复的全分列。
示例 1：
[*]输入：nums =
[*]输出： [, , ]
示例 2：
[*]输入：nums =
[*]输出：[,,,,,]
本题和上题区别：有重复元素！！！
使用树层去重。
重点：
[*] 树层去重，因为进行了回溯操纵，所以之前同一层另一个分枝使用过的标记true已经被变为false，所以false才continue；
[*] 树枝去重， 因为没有进行回溯操纵，所以上一层使用过的标记true还是true，所以true才continue。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used == true，说明同一树枝nums使用过
// used == false，说明同一树层nums使用过
// 如果同一树层nums使用过则直接跳过
if (i > 0 && nums == nums && used == false) {
continue;
}
if (used == false) {
used = true;
path.push_back(nums);
backtracking(nums, used);
path.pop_back();
used = false;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 排序
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]