题目链接：491.递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
文章讲解/视频讲解：https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
按照回溯的方法来解决。
用回溯的方式遍历数组nums构成的子序列的树的所有节点，然后判断每个节点是否构成有序。
横向遍历是遍历子序列当前下标，纵向遍历是递归寻找子序列的下一个下标。
这里需要判断去重，去重的方法是：横向遍历过程中，判断该下标对应的元素是否已遍历过，如果已遍历过，则跳过。因为对于同一层来说，元素如果重复，构成的子序列可能有重复
去重的判断可以按照我写的用循环来判断，也可以用一个哈希表来判断去重。
class Solution {
public:
vector<vector<int>> results;
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<int> path;
backtracking(path, 0, nums);
return results;
}
void backtracking(vector<int>& path, int starti, const vector<int>& nums){
if(path.size() >= 2){
if(isValid(path)) results.push_back(path);
}
for(int i = starti;i<nums.size();i++){
if(i > starti){
bool skip = false;
for(int j = starti;j<i;j++){
if(nums[j] == nums[i]){
skip = true;
break;
}
}
if(skip) continue;
}
path.push_back(nums[i]);
backtracking(path, i + 1, nums);
path.pop_back();
}
}
bool isValid(const vector<int>& path){
for(int i = 1;i<path.size();i++){
if(path[i] < path[i - 1]) return false;
}
return true;
}
};
题目链接：46.全排列
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
文章讲解/视频讲解：https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
用回溯的方法，不过我这里使用的方法比较暴力。
回溯函数的参数只有当前组合path，以及对于数组nums的引用。
横向遍历是寻找组合的当前元素，纵向遍历是寻找下一个添加入组合的元素。
其中添加当前元素时的判断我写得很粗暴，只要当前元素不在path中，就添加入结果，开启下一层遍历。
当path的大小等于nums的大小时，将path添加进最终结果。
看了卡哥的教程，发现他也写得如此暴力。。不过，可以用一个used数组来判断元素是否加入过path。
// 原写法
class Solution {
public:
vector<vector<int>> results;
vector<int> used;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
used.resize(nums.size(), false);
backtracking(path, nums);
return results;
}
void backtracking(vector<int> path, const vector<int>& nums){
if(path.size() == nums.size()){
results.push_back(path);
}
for(int i = 0;i<nums.size();i++){
if(used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(path, nums);
path.pop_back();
used[i] = false;
}
}
bool visited(const vector<int>& path, int element){
for(int i = 0;i<path.size();i++){
if(path[i] == element) return true;
}
return false;
}
};
// 用used数组判断元素是否加入
class Solution {
public:
vector<vector<int>> results;
vector<int> used;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
used.resize(nums.size(), false);
backtracking(path, nums);
return results;
}
void backtracking(vector<int> path, const vector<int>& nums){
if(path.size() == nums.size()){
results.push_back(path);
}
for(int i = 0;i<nums.size();i++){
if(used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(path, nums);
path.pop_back();
used[i] = false;
}
}
};
题目链接：47.全排列 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
文章讲解/视频讲解：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
与上一题全排列类似的思路，回溯函数的参数中只有当前排列的路径path以及对原数组nums的引用。
分为横向和纵向两个维度的遍历，横向遍历是遍历当前元素，添加入路径path，纵向遍历是递归地遍历path的下一个元素。
横向遍历时使用一个used数组，来判断当前下标是否遍历过。此题给定的是一个包含重复数字的数组，因此还需要去重。
去重是横向遍历时需要做的事情，可以使用一个unordered_set，在每一层遍历时，判断当前遍历的元素是否已经遍历过，如果遍历过，那么就跳过。因为如果同一层遍历到重复的元素，最终的结果必定重复。
也可以不用unordered_set，对nums排序，然后在横向遍历时，判断当前元素与上一个元素是否相同，如果相同则跳过。
这个used[i-1] = true，used[i-1] = false的判断是真抽象，好难想。
本质上if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;与
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1]) continue;这两条语句，保留的是两组相同的结果，但是路径不同。
如果用if(i > 0 && nums[i] == nums[i - 1]) continue;替代的话，等于是把这两组路径全丢弃了。
我之前用unordered_set来去重的方法，本质是判断同一层used[i- 1]是否使用过，与
if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;是等价的，路径相同。
// 哈希表去重
class Solution {
public:
vector<vector<int>> results;
vector<bool> used;
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> path;
used.resize(nums.size(), false);
backtracking(path, nums);
return results;
}
void backtracking(vector<int>& path, const vector<int>& nums){
if(path.size() == nums.size()){
results.push_back(path);
return;
}
unordered_set<int> hashSet;
for(int i = 0;i<nums.size();i++){
if(used[i]) continue;
if(hashSet.find(nums[i]) != hashSet.end()) continue;
hashSet.insert(nums[i]);
used[i] = true;
path.push_back(nums[i]);
backtracking(path, nums);
path.pop_back();
used[i] = false;
}
}
};
// 去重的第二种写法
class Solution {
public:
vector<vector<int>> results;
vector<bool> used;
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> path;
used.resize(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(path, nums);
return results;
}
void backtracking(vector<int>& path, const vector<int>& nums){
if(path.size() == nums.size()){
results.push_back(path);
return;
}
for(int i = 0;i<nums.size();i++){
// used[i - 1] == true，说明当前子树路径nums[i - 1]使用过
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
if(!used[i]){
used[i] = true;
path.push_back(nums[i]);
backtracking(path, nums);
path.pop_back();
used[i] = false;
}
}
}
};