组合

原题：

组合给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

  1. 输入: n = 4, k = 2
  2. 输出:
  3. [
  4.   [2,4],
  5.   [3,4],
  6.   [2,3],
  7.   [1,2],
  8.   [1,3],
  9.   [1,4],
  10. ]

解题方法：

解法一：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> subres;
    vector<vector<int>> combine(int n, int k) {

        backtracking(1, n, k);

        return res;
    }

    void backtracking(int i, int n, int k)
    {
        if (subres.size() == k)
        {
            res.push_back(subres);
            return;
        }
        for (int _i = i; _i <= n; _i++)
        {
            subres.push_back(_i);
            backtracking(_i + 1, n, k);
            subres.pop_back();
        }   
    }
};

做题小结：

经典回溯算法，但是理解还不够，需要进一步理解

根据视频学习回溯算法的基本理论

下面是回溯算法的一般框架，取自“代码随想录”公众号

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}