491. 递增子序列
思路
这个题中不能对这个序列进行重新排序，因此需要用到set进行去重
实现
点击查看代码
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backTracking(nums, 0);
return result;
}
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int>& nums, int startIndex) {
if(path.size() >= 2) {
result.push_back(path);
}
unordered_set<int> set;
for(int i = startIndex; i < nums.size(); i++) {
if(!path.empty() &&nums[i] < path.back()) continue;
if(set.find(nums[i]) != set.end()) continue;
set.insert(nums[i]);
path.push_back(nums[i]);
backTracking(nums, i+1);
path.pop_back();
}
}
};
46. 全排列
思路
因为全排列不能使用startIndex，需要使用used来记录是否使用过。
实现
点击查看代码
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
backTracking(nums, uset);
return result;
}
vector<int> path;
vector<vector<int>> result;
unordered_set<int> uset;
void backTracking(vector<int>& nums, unordered_set<int> uset) {
if(path.size() == nums.size()) {
result.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++) {
if(uset.find(nums[i]) != uset.end()) continue;
path.push_back(nums[i]);
uset.insert(nums[i]);
backTracking(nums, uset);
path.pop_back();
uset.erase(nums[i]);
}
}
};
47. 全排列 II
思路
使用used进行树枝的去重
实现
点击查看代码
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backTracking(nums,used);
return result;
}
vector<int> path;
vector<vector<int>> result;
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(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
if(used[i] == false) {
path.push_back(nums[i]);
used[i] = true;
backTracking(nums,used);
used[i] = false;
path.pop_back();
}
}
}
};