学习打卡---回溯

回溯，所有回溯都可以转换成树形结构进行解决

我们将树形结构分为纵向和横向两个方面
递归是纵向循环，也就是纵向方面，到了叶子节点就收网回溯
循环是横向循环，也就是横向方面，到了数组末尾就结束
回溯属于是将二叉树的子节点状态回归到了其父节点时的状态，说白了，就好比循环，哪怕循环变量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