491. 递增子序列
题目链接：https://leetcode.cn/problems/non-decreasing-subsequences/
算法思想：
回溯。
重要的是去重的逻辑。
在同一层for循环中，不能出现重复，比如4 7 6 7 8
第二个7产出的子集，一定会包含于第一个7的结果中，所以可以采用一个set进行记录。
class Solution {
public:
vector> final;
vector path;
void huisu(vector& nums, int pre, int start)
{
if(path.size()>1)
{
final.push_back(path);
}
unordered_set myset;
for(int i=start;i
{
// cout<<"pre:"<
if(nums[i]
continue;
if(myset.find(nums[i]) != myset.end())
continue;
myset.insert(nums[i]);
// if(i!=start && nums[i]==nums[i-1])
// continue;
path.push_back(nums[i]);
huisu(nums, nums[i], i+1);
path.pop_back();
}
}
vector> findSubsequences(vector& nums) {
huisu(nums, INT_MIN, 0);
return final;
}
46. 全排列
题目链接：https://leetcode.cn/problems/permutations/
算法思想：
回溯的思想。
排列问题和组合问题不同，元素可以重复使用，因此i可以从0开始。但是同一个递归路径上元素不能重复，所以需要查找是否之前path已经加入过了。
class Solution {
public:
vector> final;
vector path;
void huisu(vector& nums)
{
if(path.size()==nums.size())
{
final.push_back(path);
return;
}
for(int i=0;i
{
if(find(path.begin(), path.end(), nums[i]) != path.end())
continue;
path.push_back(nums[i]);
huisu(nums);
path.pop_back();
}
}
vector> permute(vector& nums) {
huisu(nums);
return final;
}
};
};
47. 全排列 II
题目链接
https://leetcode.cn/problems/permutations-ii/
算法思想：
回溯算法。
需要做树层上的去重和树枝上的去重。
class Solution {
public:
vector> final;
vector path;
void huisu(vector& nums, vector& used)
{
if(path.size()==nums.size())
{
final.push_back(path);
return;
}
for(int i=0;i
{
if(i!=0&&nums[i]==nums[i-1] && used[i-1]==0) //如果遇到相同的元素了，而且前一个元素没有使用过
continue;
if(used[i]==1)
continue;
used[i] = 1;
path.push_back(nums[i]);
huisu(nums, used);
path.pop_back();
used[i] = 0;
}
}
vector> permuteUnique(vector& nums) {
sort(nums.begin(), nums.end());
vector used(nums.size(), 0);
huisu(nums, used);
return final;
}
};
