组合问题（二叉树，递归，回溯算法）

77. 组合 - 力扣（LeetCode）

class Solution {
private:vector<vector<int>>result;vector<int>path;void backstracking(int n,int k,int startIndex){if(path.size()==k){result.push_back(path);return;}for(int i=startIndex;i<=n;i++){path.push_back(i);backstracking(n,k,i+1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backstracking(n,k,1);return result;}
};

在去组合数的过程可以理解为类似于二叉树形式的表现：

 在组合数的情况下，选择前序遍历。

为了防止重复（出现12，21）这种情况，定义一个startIndex储存遍历到数字，之后值遍历这个数字之后的数。

终止条件：在每一次遍历到叶子节点时，path数组的大小为定义的k值，则将这次遍历到达数组push进结果数组。由于遍历到底，所以要返回到上一层递归。

单层递归逻辑：从startIndex后循环遍历，将每一个循环到的值push进path数组中（path数组专门存放每一个叶子节点），递归函数，向下递归，startIndex的值也向下加一，每次函数循环结束时，还应将刚加进去的数pop出去，向前回溯，这样才能取全所有情况，如果不回溯，下一次循环的i值就会加入path数组中。