回溯，所有回溯都可以轉換成樹形結構進行解決

我們將樹形結構分為縱向和橫向兩個方面
遞歸是縱向循環，也就是縱向方面，到了葉子節點就收網回溯
循環是橫向循環，也就是橫向方面，到了數組末尾就結束
回溯屬于是將二叉樹的子節點狀態回歸到了其父節點時的狀態，說白了，就好比循環，哪怕循環變量i被利用了無數次，只要i的值不發生變化，那么循環就始終不會更改它的目標

回溯模板
void backtracking(參數) {
? ? if (終止條件) {
? ? ? ? 存放結果;
? ? ? ? return;
? ? }

? ? for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
? ? ? ? 處理節點;
? ? ? ? backtracking(路徑，選擇列表); // 遞歸
? ? ? ? 回溯，撤銷處理結果
? ? }
}

k其實就已經限制樹的深度，因為就取k個元素，樹再往下深了沒有意義
注意樹深的限制，該限制可以幫我們找到葉子節點從而得到結果
葉子節點就是要收集的結果集，其實這也不一定，沒準題目要你把所有節點都搜集一遍

回溯問題的經典概述? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 組合問題：N個數里面按一定規則找出k個數的集合
排列問題：N個數按一定規則全排列，有幾種排列方式
切割問題：一個字符串按一定規則有幾種切割方式
子集問題：一個N個數的集合里有多少符合條件的子集
棋盤問題：N皇后，解數獨等等

for循環橫向遍歷，遞歸縱向遍歷，回溯不斷調整結果集
剪枝精髓是：for循環在尋找起點的時候要有一個范圍，如果這個起點到集合終止之間的元素已經不夠 題目要求的k個元素了，就沒有必要搜索了。
所以我們要去重的是同一樹層上的“使用過”，同一樹枝上的都是一個組合里的元素，不用去重
同一樹層是for循環，而同一樹枝是遞歸

強調一下，樹層去重的話，需要對數組排序，但樹枝可能不會重復

樹層是同一個父節點的不斷追加，如果數層出現重復需要進行修改，則需要回到從父結點看起

打個比方

1,1,2

1? ? ? ? ? ? ? ? ? ? 1 ????????????????2

11? ? ?12? ? ? ? ? 12? ? ? ? ? ? ??

112

第一個1：1指向11，12

第二個1：1指向12

如何判斷該樹層重復，就需要回到最根本的父節點，父節點的遞歸中，如果這個點和上一個點相同，并且上一個點并沒有被訪問過，那就說明這是一個重復樹枝(該點與上一個點相同，重復：且上一個點沒被訪問過，獨立樹枝)

樹枝就不大可能重復了

樹枝是同一個前綴的不斷追加

遞歸中調用的元素屬于本層元素，不會被遞歸傳遞到下一層，這些本層元素一直在該層，直到遞歸中的歸到來
從遞的角度來看，層數一層層向下，這些本層元素好像并沒有什么效果，一旦通過歸回到了該層，這些本層元素會發揮它們應有的作用，維護著本層的秩序和規則
class Solution {
public:
? ? vector<vector<int>>res;
? ? vector<int>path;
? ? void dfs(vector<int>&nums,int startindex)
? ? {
? ? ? ? if(path.size()>1) res.push_back(path);
? ? ? ? if(startindex>nums.size())
? ? ? ? {
? ? ? ? ? ? return;
? ? ? ? }

? ? ? ? unordered_set<int>uset;
? ? ? ? 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]);
? ? ? ? ? ? dfs(nums,i+1);
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> findSubsequences(vector<int>& nums) {
? ? ? ? dfs(nums,0);
? ? ? ? return res;
? ? }
};

本文部分代碼和資料來自代碼隨想錄,感謝代碼隨想錄，感謝程序員Carl