題目一：子集
問題描述
78. 子集 - 力扣（LeetCode）
給你一個整數數組?nums?，數組中的元素?互不相同?。返回該數組所有可能的子集（冪集）。
解集?不能?包含重復的子集。你可以按?任意順序?返回解集。
示例 1：
輸入：nums = [1,2,3] 輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
輸入：nums = [0] 輸出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums?中的所有元素?互不相同
解題步驟
根據前面的做題經驗，這一題應該比較容易AC
有沒有覺得數組所有可能的子集很像我們每一層遍歷的結果，
所以關于子集問題，我們需要的結果不是葉子結點，而是所有結點
那么其它代碼邏輯不變，我們只需要改一下收集結果的位置即可
把result.push_back(path);這行代碼從終止條件中拿出來
就表示我們每一步都會執行這一句，
空集是所有集合的子集，那么剛調用這個backtracking函數我們就會先加入[]
后面就是遍歷一下就加入一下，輸出順序是縱深的，因為這里用的遞歸調用
對于終止條件，即用完數組所有元素，
那么我們用于指向遍歷元素的startindex必然大于等于nums.size()
但其實也可以不加終止條件，因為我們的for循環會讓i<nums.size(),它已經結束了
完整代碼如下！
code
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startindex){//返回的是每個結點result.push_back(path);if(startindex>=nums.size()){return;}for(int i=startindex;i<nums.size();i++){path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return result;}
};題目二：子集②
問題描述
90. 子集 II - 力扣（LeetCode）
給你一個整數數組?nums?，其中可能包含重復元素，請你返回該數組所有可能的?子集（冪集）。
解集?不能?包含重復的子集。返回的解集中，子集可以按?任意順序?排列。
示例 1：
輸入：nums = [1,2,2] 輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
輸入：nums = [0] 輸出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
解題步驟
這題與上一題的區別就在于nums數組中可能包含重復元素
那么這個關鍵點和我們之前做過的組合總和②是一樣的處理
重點就在于去重
我們需要排掉所有在同一層上相同的結果
但同時保證縱向不會被誤判，因為縱向取數產生的數字重復，并不意味著答案重復
縱向是不斷把子集變長的過程，加進來的都是從數組中取出的，
取出動作并不存在重復，哪怕數字一樣但它不是從nums的同一位置取出的！
所以這一題我們要在單層遍歷中加入去重代碼即可
if(i>0 && nums[i]==nums[i-1] && used[i-1]==False)
為了方便判斷重復元素，我們在主函數中會先對nums數組進行排序
那么遍歷到第i個元素就可以通過?nums[i]==nums[i-1]這個代碼判斷是否出現重復元素
為了保證nums[i-1]合法，所以i必須大于0，
因為每次操作我們會用used數組標記數字的使用情況，
在縱向的遞歸中，used[i]=used[i-1]=true
但在同層當中，由于前一步存在回溯，我們的used[i-1]==false
翻譯一下就是，上一層用過后放回去假裝沒用過
符合以上條件就是我們的重復元素，那么直接continue不需要繼續執行
完整代碼如下，需要注意在主函數中定義used數組和對nums數組進行排序！
code
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startindex,vector<bool>& used){//返回的是每個結點result.push_back(path);for(int i=startindex;i<nums.size();i++){if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){//去重continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,i+1,used);used[i]=false;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return result;}
};題目三：非遞減子序列
問題描述
491. 非遞減子序列 - 力扣（LeetCode）
給你一個整數數組?nums?，找出并返回所有該數組中不同的遞增子序列，遞增子序列中?至少有兩個元素?。你可以按?任意順序?返回答案。
數組中可能含有重復元素，如出現兩個整數相等，也可以視作遞增序列的一種特殊情況。
示例 1：
輸入：nums = [4,6,7,7] 輸出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
輸入：nums = [4,4,3,2,1] 輸出：[[4,4]]
提示：
1 <= nums.length <= 15-100 <= nums[i] <= 100
解題步驟
這一題可以看成上一題的升級版，它在要求不重復的情況下同時要求該子序列遞增
但需要注意的是這里的子序列是按照原數組排序生成的，
我們不能使用sort函數，不然結果也是不正確的
所以我們要換一種去重邏輯
但仍舊需要做到只除去同一層的重復項
不除去縱向的重復元素
那么排序不能用，used數組也就不能用了，
我們需要一個新的輔助，對于去重首選unordered_set，
可以利用find函數很快檢查到是否已經出現過
那么我們在處理這一層元素前就需要先定義好這個uset
unordered_ser<int> uset;
再進入到遍歷邏輯中，挨個檢查元素是否符合題意
如果該元素之前已經用過，那么它必然可以在uset中找到
所以第一個不符合的情況是
if(uset.find(nums[i])!=uset.end())
要確保子序列遞增，那么nums[i]不能小于當前path的最后一個元素，即path.back()
為防止出現path為空時的錯誤，先判斷path.empty()為false
則第二個不符合情況如下
if(!path.empty() && nums[i]<path.back)
?可以合并這兩種情況，continue
沒有出現以上情況，則處理該結點
把nums[i]加入uset中做記錄
再加入該數到path中
遞歸調用后回溯
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
這里的uset不需要回溯，因為我們在每一層使用它，
如果是遞歸會重新定義，內容被清空不影響判斷去重?
此外在加入結果到result數組中時，我們要先判斷path.size()>=2，
這也是題目條件之一，要求子序列長度大于等于2
if(path.size()>=2){
? ? ? ? result.push_back(path);
}
組合所有代碼，即可得到完整版如下方！?
code
class Solution {
public: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> uset; // 使用set來對本層元素進行去重for(int i=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();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return result;}
};
