1.问题

77. 组合 - 力扣（LeetCode）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

2.思路

        使用回溯法求解该问题其结构类似于树。如下所示。层数代表递归的次数由k控制，每层的节点数由n控制。

 3.代码实现

 vector<vector<int>> result;
    vector<int> path;

    void backrack(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);
            backrack(n,k,i+1);
            path.pop_back();
        }
    }

组合问题的优化

        在进行遍历的时候，发现有的分支完全没有遍历的必要，因此可以通过剪枝来优化组合问题。如图所示。

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 所需需要的元素个数为: k - path.size();

3. 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）

4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

代码优化

   vector<vector<int>> result;
    vector<int> path;

    void backrack(int n,int k,int startindex){
         if(path.size()==k){
            result.push_back(path);
            return ;
        }
        for(int i=startindex;i<=n-(k-path.size())+1;i++){
            path.push_back(i);
            backrack(n,k,i+1);
            path.pop_back();
        }
    }