真正的全排列—深度优先搜索

#include<stdio.h>
//c语言的全局变量在没有赋值以前默认为0.因此这里的book数组无需再次赋初 始值0
int a[10],book[10],n;

void dfs(int step){//如果站在第n+1个盒子面前，则表示前n个盒子已经放好 扑克牌
    int i;
    if (step == n + 1){ //如果站在n+1的位子上，则说明前面n个盒子已经放好扑克牌了
        //输出（1~n号盒子中的扑克牌编号）
        for (i = 1 ; i <= n ; i ++)
            printf("%d",a[i]);
        printf("\n");
        return;
    }
    //此时站在第step盒子面前，应该放哪张牌呢？
    //按照1、2、3...n顺序尝试
    for (i = 1; i <= n ; i ++){
        //判断扑克牌i是否还是手上
        if (book[i] == 0) // 等于0表示i号扑克牌在手上
        {
            //开始尝试使用扑克牌i
            a[step] = i; // 将i号扑克牌放到第step个盒子中
            book[i] = 1; //将book[i]设为1，表示i号扑克牌已经不在手上

            //第step个盒子已经放好扑克牌，接下来需要走到下一个盒子面前
            dfs(step + 1);//通过递归实现
            book[i] = 0; //这是非常重要一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }return;
}

int main(){
    scanf("%d",&n); //输入的时候要注意n为1~n之间的整数
    dfs(1);
    return 0;
}

运行结果：

坑爹奥数

#include<stdio.h>
int a[10],book[10],total = 0;

void dfs(int step){
    int i;
    if (step == 10){
        if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == a[7] * 100 + a[8] * 10 + a[9]){
            total++;
            printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
        }

    return ;
    }


    for (i = 1 ; i <= 9 ; i ++){
        if (book[i] == 0){
            a[step] = i;
            book[i] = 1;

            dfs(step+1);
            book[i] = 0;
        }
    }
    return;
}

int main(){
    dfs(1);
    printf("total=%d\n",total/2);
    return 0;
}

执行结果: