排列与组合(非递归的DFS算法)
组合的生成与排列相似,组合中数字相同顺序不同的可以归纳为一个组合,可以按升序生成或降序生成,即后面搜索到的数要大于(或小于)前面的数,我在这里以升序为例。
#include <stdio.h>
void comb(int m,int n)
{
int t,k,i,a[20];
k=1;
t=0;
a[0]=0;
a[k]=0;
while(k>0){
a[k]++; //向下搜索
while((a[k]<=m)&&(a[k]<=a[k-1]))a[k]++; //判断当前结点是不是可行的,若不是则在容许范围内继续搜索
if(a[k]<=m){ //有没有超出范围
if(k==n) { //是不是目标解
for(i=1;i<=n;i++)
printf("%d",a[i]);
t++; //输出完毕回溯到上一层,继续搜索其他解
k--;
printf("\n");
}
else { //不是则进行下一层的搜索
k++;
a[k]=0;
}
}
else k--; //若当前状态找不到可行的解则回溯
}
printf("sum:%d",t);
}
int main()
{
int m,n;
scanf("%d%d",&m,&n);
comb(m,n);
return 0;
}
#include <iostream> //组合
using namespace std;
int n[1001], vtd[1001], digits, nums;
void dfs(int x, int crnt);
int main()
…… …… 余下全文