day 24 第七章 回溯算法part01

● 理论基础
本质上还是穷举遍历，伴随着递归

回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
● 77. 组合

/*
 * 77. 组合
中等
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
 */

class Solution_77 {
 public:
  /*
   * 回溯
回溯
输入参数为区间的元素
终止条件为单次搜索结果大小大于k
单层回溯逻辑：
    判断终止条件
    先横向遍历取一个值
    纵向遍历取一个值
    回溯()
   */

  void back(int cur, int n, int k, vector<vector<int>> &res, vector<int> &path){
      if(path.size() == k) {
          res.push_back(path);
          return;
      }
      for(int i = cur; i <= n - (k - path.size()) + 1; i++){//剪枝，当剩余元素数量不足以构成k个元素时就不用再搜索了
          path.push_back(i);
          back(i + 1, n, k, res, path);
          path.pop_back();
      }
  }

  vector<vector<int>> combine(int n, int k) {
      vector<vector<int>> res;
      vector<int> path;
      back(1, n, k, res, path);
      return res;
  }
};