1. 从1-n这n(n<20)个整数中随机选择任意多个,输出所有可能的选择方案。

int n;
vector<int> v;
inline int dg(int t)
{
    if(t>n){//递归边界 调试的时候要看一下只有一个等极端数据对不对
        if(v.size()==0) cout<<"空集"<<endl;
        else{
                for(int i=0; i<v.size(); ++i) printf("%d ",v[i]);
                cout<<endl;
        }
    }else{/*递归树左右子树顺序根据最方便还原现场的方法去写,
        也就是根左右和跟右左是等效的,
        但是递归从根到叶再到根的顺序是固定的*/

        //左边的分支(可以看成边,也就是转换条件)
        dg(t+1);//下一层递归,可以看成是递归树上当前节点的左右子树
        //还原现场(根据边上的转换条件进行现场还原,因为要保持左右边进入时初始状态都是当前结点状态)

        v.push_back(t);//右边的分支
        dg(t+1);//递归树当前节点左右子树
        v.pop_back();//还原现场
    }
}
int main(){
    while(1){
        cin>>n;
        dg(1);//最大最完整的一棵递归树,当前状态处于根节点
    }
    return 0;
}

2. 把1-n这n(n<10)个整数排成一行后随机打乱顺序,输出所有可能的次序。(全排列)

int n;
int a[maxn];
int main()
{
    while(1){
        sc(n);
        for(int i=1;i<=n;++i) a[i-1]=i;
        do{
            for(int i=0;i<n;++i) printf("%d ",a[i]);
            cout<<endl;
        }while(next_permutation(a,a+n));
    }
    return 0;
}

3.把1-n这n(n<10)个整数排成一行后随机打乱顺序,输出所有可能的次序。(递归)

int order[maxn];
bool chosen[maxn];
int n;
bool dg(int x){
    if(x>=n){
        for(int i=0; i<n; ++i) printf("%d ",order[i]);
        cout<<endl;
    }else{
        for(int i=1; i<=n; ++i)//当前递归树有n个分支,接下来dfs每个分支
            if(!chosen[i]){
                chosen[i]=1;
                order[x]=i;
                dg(x+1);
                //还原结点是为了进入同一层递归结点的时候初始状态是一样的
                chosen[i]=0;
            }
    }
}
int main(){
    while(1){
        sc(n);
        for(int i=0;i<=n;++i) order[i]=0;
        dg(0);//从第0个位置开始
    }
    return 0;
}
01-16 11:36