题目

设n个整数的集合{1,2,3,,,n},从中取出r个进行排序（r<n）,试列出所有可能。

代码

#include <iostream>
using namespace std;
int n,r;
int a[1001];
int b[1001]={0};
int total=0;
void print(){
    total++;
    for(int i=1;i<=r;i++) cout<<a[i]<<" ";
    cout<<endl;
}
void search(int k){
    for(int i=1;i<=n;i++){
        if(!b[i]){
            a[k]=i;
            b[i]=1;
            if(k==r) print();
            else search(k+1);
            b[i]=0;
        }
    }
}
int main(){
    cin>>n>>r;
    search(1);
    cout<<total;
    }

分析

套模版练习题

1 for循环范围

即可选范围，对于任意k层，1～n中任何一个数都可选，故for循环范围为1～n

    for(int i=1;i<=n;i++)

2 可选条件

只要没用使用过都可选，用一个数组b表示是否使用过，若i使用过，则把b[i]设为1，入b[10]没用使用过，则b[10]=0;

if(!b[i])

3 选择后的变化

• 第k层，就是在选第k个数，即 a[k]=i;
• i被选中，b[i]设为1

if(!b[i]){
            a[k]=i;
            b[i]=1;
      
        }

4 结束条件

• 如果，k==r,则选完了，输出
• 否则下一层

if(!b[i]){
            a[k]=i;
            b[i]=1;
            if(k==r) print();
            else search(k+1);
        }

5 回溯

• 只需要去掉选中状态，b[i]=0即可。
• 数组a无需处理，重新赋值就直接覆盖了。

if(!b[i]){
            a[k]=i;
            b[i]=1;
            if(k==r) print();
            else search(k+1);
            b[i]=0;
        }