491.?遞增子序列
思路：
這道題和子集2不同的地方在于本題不能進行排序，排序之后會出現(xiàn)新的子集，不和題意。本題可以用一個set類型的變量來記錄先前已經(jīng)遍歷過的數(shù)組，如果先前已經(jīng)遍歷了，后續(xù)就不用再遍歷。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(vector<int>& nums,int index)
? ? {
? ? ? ? if(path.size()>1)res.push_back(path);
? ? ? ? unordered_set<int> usedset;
? ? ? ? for(int i=index;i<nums.size();i++)
? ? ? ? {
? ? ? ? if ((!path.empty() && nums[i] < path.back())|| usedset.find(nums[i]) != usedset.end())
? ? ? ? {
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? usedset.insert(nums[i]);
? ? ? ? path.push_back(nums[i]);
? ? ? ? backtracking(nums,i+1);
? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> findSubsequences(vector<int>& nums) {
? ? ? ? backtracking(nums,0);
? ? ? ? return res;
? ? }
};
46.?全排列
思路：
這道題是排列問題，123與213是屬于兩個排列，這與以往的組合問題不一樣。本題使用布爾類型的數(shù)組used來標記哪一位已經(jīng)使用過，在每層遍歷的過程中都從第一個元素開始遍歷，但是如果使用了就跳過。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(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[i]==true)continue;
? ? ? ? ? ? path.push_back(nums[i]);
? ? ? ? ? ? used[i]=true;
? ? ? ? ? ? backtracking(nums,used);
? ? ? ? ? ? used[i]=false;
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> permute(vector<int>& nums) {
? ? ? ? vector<bool> used(nums.size(),false);
? ? ? ? sort(nums.begin(),nums.end());
? ? ? ? backtracking(nums,used);
? ? ? ? return res;
? ? }
};
47.?全排列 II
思路：
這道題的思路和第46題一致，只不過題目給定的數(shù)組中含有重復的元素，所以在進行排列之前先進行去重操作，去重的算法與第40題一致。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(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 && used[i-1]==false && nums[i]==nums[i-1])continue;
? ? ? ? ? ? if(used[i]==true)continue;
? ? ? ? ? ? path.push_back(nums[i]);
? ? ? ? ? ? used[i]=true;
? ? ? ? ? ? backtracking(nums,used);
? ? ? ? ? ? used[i]=false;
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> permuteUnique(vector<int>& nums) {
? ? ? ? vector<bool> used(nums.size(),false);
? ? ? ? sort(nums.begin(),nums.end());
? ? ? ? backtracking(nums,used);
? ? ? ? return res;
? ? }
};
