自然数拆分
利用step记录组合情况，只用sum不能判断组合情况
1.选择dfs原因：产生排列组合，和为7，step为8，其中7个空位，第8个step为输出；
参量的设置sum，step (进入下一层）;
2.终止条件：sum>7 剪枝干 (此时最终step不一定为8)！！！！！
3.输出条件：sum==7，注意最后的值和前面的值输出形式不同；
4.dfs递归--for循环的设置：i为（1-7）需要放入每层的值；
5.注意：标记问题：同一数可以重复使用
组合问题：i 从上一层的值开始递增7结束i=a[step-1]，同时注意a[0]边界
回溯问题：sum+=i; dfs（step+1); sum-=i; 等价于 dfs（sum+i，step+1）
因为这一层的sum没有改变
#include<stdio.h>#include<string.h>int n;int a[1000];void dfs(int sum,int step){if(sum>n) return ; //注意！！！！！边界情况if(sum==n){for(int i=0;i<=step-2;i++)printf("%d+",a[i]);printf("%d\n",a[step-1]);return ;}//组合,可重复，从上一层最小值开始//同时注意初始边界值a[step-1]for(int i=a[step-1];i<n;i++){a[step]=i;//放入dfs(sum+i,step+1); //递归//这里无需标记，组合可重复使用}}int main(){scanf("%d",&n);a[0]=1;dfs(0,1);return 0;}
八皇后
1.解题关键：横竖斜只有1个皇后；斜：横纵坐标之和，横纵坐标之差
2.dfs参数设置：step，不用调用每层x，y，不是迷宫探险类，只用check二维数组上每一点
3.for循环设置：check，该step层皇后是否满足check；
4.终止条件：step==n+1；
注意：i 行，a[ i ]列
#include<stdio.h>int n,a[20]; //i表示行，a[i]表示列；int cnt=0;int check(int x,int y)//n皇后是否成立，check游戏标准：横竖斜仅有一个皇后；{for(int i=1; i<=x; i++) //无需讨论行==情况，每次放step都是一行一行放的{if(a[i]==y)return 0; //皇后位置和其他皇后列==（×）if(i+a[i]==x+y)return 0; //皇后位置和其他皇后对角线1（×）if(i-a[i]==x-y)return 0; //皇后位置和其他皇后对角线2（×）}return 1;}void dfs(int step) //表示第step个皇后放在何处{if(step==n+1)//dfs最后一层为输出{cnt++; //解的个数if(cnt<=3){for(int i=1; i<=n; i++){printf("%d ",a[i]);if(i%n==0)printf("\n");}}return ;}for(int j=1; j<=n; j++) //共1-8列{if(check(step,j)) //check第step行的皇后是否能放在j列上{a[step]=j;//放在j列，标记；dfs(step+1); //进入下一层，放下一个皇后；a[step]=0;//取消标记}}}int main(){scanf("%d",&n);dfs(1); //第一层开始printf("%d",cnt); return 0; }
如果觉得《刷题刷题。》对你有帮助，请点赞、收藏，并留下你的观点哦！
