python/C++课程/待整理知识/啊哈算法/p54_dfs.cpp

#include<stdio.h>

int a[10];//开一个数组，用来装每一位的数字,3位一个数，共9位,把索引值为0的不要，计10个
int book[10] = { 0 }; //标记哪个数是否用过了，初始值全是0，表示都没用过
int total = 0; //一共多少个解

void dfs(int step) {
	int i;
	//到第10步，就不用再计算了，可以出结果了
	if (step == 9 + 1) {
		//发现有符合条件的就记录下来
		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;
}