491.遞增子序列
回溯三部曲
遞歸函數(shù)參數(shù)
本題求子序列涧卵，很明顯一個元素不能重復使用勤家，所以需要startIndex，調(diào)整下一層遞歸的起始位置
遞增子序列大小至少為2
單層搜索邏輯
使用set來對本層元素進行去重
unordered_set<int>uset;// 使用set來對本層元素進行去重for(inti=startIndex;i<nums.size();i++){if((!path.empty()&&nums[i]<path.back())||uset.find(nums[i])!=uset.end()){continue;}uset.insert(nums[i]);// 記錄這個元素在本層用過了柳恐，本層后面不能再用了path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}
巧妙的是可以用數(shù)組標記是否使用過伐脖。
46.全排列
排列問題和組合有區(qū)別
回溯三部曲
遞歸函數(shù)參數(shù)
需要一個used數(shù)組，標記已經(jīng)選擇的元素
遞歸終止條件
當收集元素的數(shù)組path的大小達到和nums數(shù)組一樣大的時候乐设，說明找到了一個全排列讼庇，也表示到達了葉子節(jié)點
單層搜索的邏輯
排列問題，每次都要從頭開始搜索?一個排列里一個元素只能使用一次
for(inti=0;i<nums.size();i++){if(used[i]==true)continue;// path里已經(jīng)收錄的元素近尚，直接跳過used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;}
47.全排列?II
同一樹層蠕啄，前一位（也就是nums[i-1]）如果使用過，那么就進行去重
voidbacktracking(vector<int>&nums,vector<bool>&used){// 此時說明找到了一組if(path.size()==nums.size()){result.push_back(path);return;}for(inti=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]==false){continue;}if(used[i]==false){used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;}}}?
