Problem P24. [算法课回溯]组合问题

采用递归遍历所有可能性，再使用剪枝减小运行时间，利用回溯，代码有注释

#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
#include<string>

using namespace std;

vector<vector<int>> result;
vector<int> path;
void dfs(int n, int k, int cur){
    // 递归结束条件
    if (path.size() == k){
        result.push_back(path);
        return;
    }
    // 剪枝， cur是现在遍历到的数值
    if (n-cur+1+path.size()<k){
        return;
    }
    path.push_back(cur);
    // 选择添加cur进组合
    dfs(n, k, cur+1);
    // 回溯
    path.pop_back();
    // 选择不添加cur进组合
    dfs(n, k, cur+1);
    return;
}

int main()
{
    int n, k;
    cin >> n >> k;
    dfs(n, k, 1);
    printf("[");
    for (int i = 0; i < result.size(); i++){
        printf("[");
        vector<int> x = result[i];
        for (int j = 0; j < x.size(); j++){
            printf("%d", x[j]);
            if (j < x.size()-1){
                printf(", ");
            }
        }
        printf("]");
        if (i < result.size()-1){
            printf(", ");
        }
    }
    printf("]");
    return 0;
}