1、回溯法
也叫试探法，实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
2、回溯法解决问题的步骤
（1）针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
（2）确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
1、问题
找出从自然数1~n中任取r个数的所有组合。
2、算法思想
按回溯法的思想，将找到的组合从小到大的顺序存放到数组a[0],a[1],…,a[r-1]中，组合中的元素满足以下性质：
a[i+1]>a[i]，后一个数大于前一个数
a[i]-i<=n-r+1，如此
3、C语言实现数的组合
#include <stdio.h>
#define MAX 100
int a[MAX];
void comb(int n, int r)
{
int i, j;
i= 0;
a[i]= 1;
do{
if(a[i]-i<=n-r+1) //还可以向前试探
{
if(i==r-1) //找到一个组合
{
for(j=0; j<r; j++) //输出一个组合
printf("%4d", a[j]);
printf("\n");
a[i]++;
continue;
}
i++; //向前试探
a[i]= a[i-1]+1;
}
else //开始回溯
{
if(i==0) //找完全部解
return; //所有解都找到了才返回，结束函数
a[--i]++;
}
}while(1);
}
void main()
{
int x, y;
printf("请规定截止数和几个数组合（用,分割的整数）：");
scanf("%d,%d",&x,&y);
printf("自然数1~%d中%d个数的任意组合有：\n", x, y);
comb(x, y);
}
高中学过的“排列组合”我们就知道是组合是不考虑顺序的，所以一眼看去就知道结果是否正确：
参考文献：《The Function and Algorithm of Program Language C/C++》