代码随想录Day25_回溯5_全排列
<h2 id="非递减子序列">非递减子序列</h2><h3 id="问题描述">问题描述</h3>
<p>给了一个数组，要求给出其所有长度>=2的非递减子序列。</p>
<h3 id="思路">思路</h3>
<p>压入结果的条件是<code>path.size()>=2</code>，回溯过程结束的条件是移动到了边上<code>startIndex>=num.size()</code><br>
在树中，非递减序列，要求压入的元素必须比之前压入的大：<code>if(path.empty()||nums>=path.back())</code></p>
<h3 id="问题">问题</h3>
<p>如果给出的数组包含重复元素，那么答案的集合中就会包含重复的数组；<br>
<img src="image-7.png"><br>
那我标记该位置的元素已经用过了，如何？````</p>
<pre><code> if(used==false&&(path.empty()||nums>=path.back()))
{
path.push_back(nums);
used=true;
backtrack(nums,i+1,used);
path.pop_back();
used=false;
}
</code></pre>
<p><img src="image-8.png"><br>
这样也是不行的，原因在于数组不同下标处的元素可能相等，这样只是标记了一个位置的该元素，但是如果该位置后面的元素和已经遍历过的元素有相同的，也会导致结果集中存在一样的数组。所以重点不是对下标记录，而是对这个元素本身的值进行记录。使用哈希容器<code>unorder_set<int> usedThisLeval</code></p>
<pre><code> for(int i=startIndex;i<nums.size();i++){
if(usedThisLeval.contains(nums)){
continue;
}
if(path.empty()||nums>=path.back())
{
path.push_back(nums);
usedThisLeval.insert(nums);
backtrack(nums,i+1);
path.pop_back();
}
}
</code></pre>
<p>但是似乎很慢！</p>
<h3 id="原始思路解法代码">原始思路解法代码</h3>
<pre><code>class Solution {
public:
vector<int>path;
set<vector<int>>res;
void backtrack(vector<int>&nums, int startIndex){
if(path.size()>=2){
res.insert(path);
}
if(startIndex>=nums.size()){
return;
}
for(int i=startIndex;i<nums.size();i++){
if(path.empty()||nums>=path.back())
{path.push_back(nums);
backtrack(nums,i+1);
path.pop_back();}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
path.clear();
res.clear();
backtrack(nums,0);
return vector<vector<int>>(res.begin(),res.end());
}
};
</code></pre>
<h2 id="全排列">全排列</h2>
<h3 id="题目描述">题目描述</h3>
<p>给定一个不含重复数字的数组，返回其所有可能的全排列。<br>
看到题目第一眼，感觉这道题和之前做过的组合问题很相似。组合问题：在n个数中找K个数的组合。复用后发现不同，N个数的组合在组合问题中是这种情况<br>
<img src="image-5.png"><br>
在回溯的这颗树中，在移动startIndex的过程中之前的数就不会考虑进来了，但是排列问题需要考虑进来。<br>
解决办法是vector<bool>& used标记状态</bool></p>
<pre><code>class Solution {
public:
vector<int>path;
vector<vector<int>>res;
void backtrack(vector<int>&nums, vector<bool>&used){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(used==true){
continue;//跳出本次循环
}
used=true;
{path.push_back(nums);
backtrack(nums,used);
path.pop_back();
used=false;}
}
}
vector<vector<int>> permute(vector<int>& nums) {
path.clear();
res.clear();
vector<bool>used(nums.size(),false);
backtrack(nums,used);
return res;
}
};
</code></pre>
<h2 id="全排列2">全排列2</h2>
<h3 id="问题理解">问题理解</h3>
<p>数组中出现了重复元素，使用暴力set去重，但是似乎是一种很慢的方法，相当于每次插入都要遍历一次所有组合。<br>
<img src="image-6.png"></p>
<h3 id="代码">代码</h3>
<pre><code>class Solution {
public:
vector<int>path;
vector<vector<int>>res;
void backtrack(vector<int>&nums, vector<bool>&used){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(i>0&&nums==nums&&used==true){
continue;//跳出本次循环
}
if(used==false){
used=true;
path.push_back(nums);
backtrack(nums,used);
path.pop_back();
used=false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
path.clear();
res.clear();
sort(nums.begin(),nums.end());
vector<bool>used(nums.size(),false);
backtrack(nums,used);
return res;
}
};
</code></pre>
<h2 id="_"></h2>
<h3 id="总结">总结</h3>
<p>在排列问题中使用startIndex来标记位置，因为排列是从后面每次都经过。但在组合问题中，答案集合是不关心位置的，固定元素的不同组合。首先对数组进行排序，使用used看是否用过。</p><br><br>
来源：https://www.cnblogs.com/ChenYinging/p/19286524
頁:
[1]