2025年回溯法——字典序组合问题

科技前沿 • 2025-03-28 08:40 • 阅读 22

大家好，我是讯享网，很高兴认识大家。

从整数 1 至 n 中选出 m 个数，按字典序排列输出。

3 2

讯享网

讯享网1 2 1 3 2 3 3

#include<iostream> #include<vector> using namespace std; class Solution { 
    private: vector<vector<int>> result;//定义一个二维数组存放符合条件结果的集合 vector<int> path;//一维数组，用来存放符合条件的结果 void backtracking(int n, int k, int startIndex) { 
    if (path.size() == k)//找到了一个子集大小为k的组合  { 
    result.push_back(path);//用result二维数组，把path保存起来  return;//终止本层递归 } for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { 
    path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); } } public: vector<vector<int>> combine(int n, int k) { 
    backtracking(n, k, 1); return result; } void print() { 
    for (int i = 0; i < result.size(); i++) { 
    for (int j = 0; j < result[i].size(); j++) { 
    cout << result[i][j]; if (j == result[i].size() - 1) cout << endl; else cout << " "; } } cout << result.size() << endl; } }; int main() { 
    Solution a; int n, k; cin >> n >> k; a.combine(n, k); a.print(); return 0; }

讯享网//这个换行格式真的写了好久 if (j == result[i].size() - 1) cout << endl; else cout << " ";

void print(){ 
    for (int i = 0; i < result.size(); i++){ 
    for (int j = 0; j < result[i].size(); j++) { 
    cout << result[i][j];//这里只能用result输出，因为path里面是空的 if (j == result[i].size() - 1) cout << endl; else cout << " "; } } cout << result.size() << endl; }

2025年回溯法——字典序组合问题

相关推荐