491.递增子序列
这道题自己写了好几种办法，发现都有漏洞。看了Carl的答案才想到可以用哈希表。
Carl用哈希表来验证是否在这颗树的同一层里已用过相同的数。这点我在之前并没有想通。现在想明白了：如果当前层用了某个数，就把这个数加到哈希表，如果list里再有这个数，就不call function了。因为如果再把这个数进行回溯计算，那他的答案（至少这一层）会是和之前 同一层有一样的结果。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int> nums, int start_index){
if(path.size()>=2){
res.push_back(path);
}
if(start_index>=nums.size()){
return ;
}
unordered_set<int> u_num;
for(int i=start_index; i<nums.size(); i++){
auto it = u_num.find(nums[i]);
if(it!=u_num.end()){
continue;
}
u_num.insert(nums[i]);
path.push_back(nums[i]);
if(validPath(path)){
backtracking(nums,i+1);
}
path.pop_back();
}
}
bool validPath(vector<int> cur_path){
for(int i=1; i<cur_path.size(); i++){
if(cur_path[i]<cur_path[i-1]){
return false;
}
}
return true;
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return res;
}
};
46.全排列
写不出来。怎么写也不对。
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[i] == true) continue; // path里已经收录的元素，直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
休息了一会，看了一遍，明白是什么意思了。
47.全排列 II
草，不想写了。什么几把玩意。绕绕绕的。妈的。
