题目描述

链接：https://ac.nowcoder.com/acm/contest/998/A 从 1\sim n1∼n这 n (n \leq 16)(n≤16) 个整数中随机选取任意多个，输出所有可能的选择方案。

输入描述

一个整数n。

输出描述

每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

思路

回溯算法

代码

#include <iostream>
#include <vector>

class mySolution{
public:
    void backtracking(int limit,int count,int order,int n){
        if(count==limit){
            this->result.push_back(this->depth);
            return;
        }
        for(int i=order;i<=n;i++){
            this->depth.push_back(i);
            this->backtracking(limit,count+1,i+1,n);
            this->depth.pop_back();
        }
    }
    
    void getResult(int n){
        for(int i=1;i<=n;i++){
            this->backtracking(i,0,1,n);
        }
    }
    
    void printResult(){
        int rows=this->result.size();
        for(int i=0;i<rows;i++){
            int cols=result[i].size();
            for(int j=0;j<cols;j++){
                std::cout<<result[i][j]<<" ";
            }
            std::cout<<std::endl;
        }
    }
    
private:
    std::vector<std::vector<int>> result;
    std::vector<int> depth;
};

int main(){
    mySolution*solution=new mySolution();
    int n;
    while(std::cin>>n){
        solution->getResult(n);
        solution->printResult();
        std::cout<<" "<<std::endl;
    }
    delete solution;
    solution=nullptr;
    return 0;
}