力扣77. 组合-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣77. 组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

递归

思路：

找到一个长度为 nnn 的序列 aaa 的所有子序列，代码框架：

std::vector<int> temp;
void dfs(int cur, int n) {
    if (cur == n + 1) {
        // 记录答案
        // ...
        return;
    }
    // 考虑选择当前位置
    temp.push_back(cur);
    dfs(cur + 1, n, k);

    temp.pop_back();
    // 考虑不选择当前位置
    dfs(cur + 1, n, k);
}

本题递归结束条件为序列中元素为 k，即：

    void dfs(int cur, int n, int k) {
        // 序列元素个数满足条件，存储结果退出
        if (item.size() == k) {
            result.push_back(item);
            return;
        }

        // 考虑选择当前位置
        item.push_back(cur);
        dfs(cur + 1, n, k);
        item.pop_back();

        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }

private:
    std::vector<int> item;
    std::vector<std::vector<int>> result;

已经构建的序列S'，剩余的数不足以构成满足条件的序列 S：
- 剩余的数长度 n - (cur - 1)
- size(S') + (n - (cur - 1)) < size(S) = k
- 这种情况也需要退出递归

综上，完整代码

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return result;
    }

private:
    void dfs(int cur, int n, int k) {
        if (item.size() + (n -cur + 1) < k) {
            return;
        }

        if (item.size() == k) {
            result.push_back(item);
            return;
        }

        item.push_back(cur);
        dfs(cur + 1, n, k);
        item.pop_back();
        dfs(cur + 1, n, k);
    }

private:
    std::vector<int> item;
    std::vector<std::vector<int>> result;
};

文章来源地址https://www.toymoban.com/news/detail-792254.html

到了这里，关于力扣77. 组合的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！