算法学习之组合问题

题目要求：

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

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

 

示例 1：

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

输入：n = 1, k = 1
输出：[[1]]
提示：

1 <= n <= 20
1 <= k <= n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations

解题代码：

class Solution {
private:
    vector<vector<int>> res;
    // 求解C(n, k)，当前已经找到的组合存储在c中，需要从start开始搜索新的元素
    void generateCombinations(int n, int k, int start, vector<int>& c) {
        if (c.size() == k) {
            res.push_back(c);
            return;
        }

        for (int i = start; i <= n; ++i) {
            c.push_back(i);
            generateCombinations(n, k, i + 1, c);
            c.pop_back();
        }

        return;
    }
public:
    vector<vector<int>> combine(int n, int k) {
        res.clear();
        if (n <= 0 || k <= 0 || k > n)
            return res;

        vector<int> c;
        generateCombinations(n, k, 1, c);

        return res;
    }
};

算法优化：

class Solution {
private:
    vector<vector<int>> res;

    // 求解C(n, k)，当前已经找到的组合存储在c中，需要从start开始搜索新的元素
    void generateCombinations(int n, int k, int start, vector<int> &c) {
        if (c.size() == k) {
            res.push_back(c);
            return;
        }

        // 还有k-c.size()个空位，[i...n]中至少有k-c.size()个元素
        // i做多为 n-(k-c.size()) +1
        for (int i = start; i <= n - (k - c.size()) + 1; ++i) {
            c.push_back(i);
            generateCombinations(n, k, i + 1, c);
            c.pop_back();
        }

        return;
    }

public:
    vector<vector<int>> combine(int n, int k) {
        res.clear();
        if (n <= 0 || k <= 0 || k > n)
            return res;

        vector<int> c;
        generateCombinations(n, k, 1, c);

        return res;
    }
};