算法学习之组合问题

Jackey C/C++ 1,211 次浏览 , 没有评论

题目要求:

给定两个整数 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;
    }
};

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

Go