回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
回溯法的一般流程和技术
在用回溯法求解有关问题的过程中，一般是一边建树，一边遍历该树。在回溯法中我们一般采用非递归方法。下面，我们给出回溯法的非递归算法的一般流程：
在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。
【问题】 组合问题
问题描述：找出从自然数1，2，…，n中任取r个数的所有组合。
采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：
(1) a[i+1]>a[i]，后一个数字比前一个大；
(2) a[i]-i<=n-r+1。
按回溯法的思想，找解过程可以叙述如下：
首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a[2]上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a[2]回溯到a[1]，这时，a[1]=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下：
[color=Red]
/* m代表可选数字个数，从1开始[1…m]，r代表组合数字的个数 */
{
int *a = new int[r];
memset(a, 0, r * sizeof(int));
int i = 0;
while (1)
{
// 达到规模，输出结果
if (a[i] – i <= m - r + 1)
{
if (i >= r – 1)
{
for (int t = 0; t < r; t++)
{
cout << *(a + t) << ;
}
cout << endl;
a[i]++;
continue;
}
}
// 满足条件，因而扩大规模
if (a[i] < m && i < r)
{
i++;
}
else
{
if (i == 0) // 退出
{
break;
}
else if (i > 0)
{
a[i] = a[i – 1] + 1;
a[–i]++; // 回溯
}
}
if (a[i] <= a[i - 1] && i > 0)
{
a[i] = a[i – 1] + 1;
}
}
}
{
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int b[8] = {0};
return 0;
}
[color]