组合问题的解决方案——回溯法

       回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。

       回溯法的一般流程和技术

       在用回溯法求解有关问题的过程中,一般是一边建树,一边遍历该树。在回溯法中我们一般采用非递归方法。下面,我们给出回溯法的非递归算法的一般流程:

       在用回溯法求解问题,也即在遍历状态空间树的过程中,如果采用非递归方法,则我们一般要用到栈的数据结构。这时,不仅可以用栈来表示正在遍历的树的结点,而且可以很方便地表示建立孩子结点和回溯过程。

      【问题】 组合问题

       问题描述:找出从自然数1,2,…,n中任取r个数的所有组合。

       采用回溯法找问题的解,将找到的组合以从小到大顺序存于a[0],a[1],…,a[r-1]中,组合的元素满足以下性质:

       (1) a[i+1]>a[i],后一个数字比前一个大;

       (2) a[i]-i[color=Red]/* m代表可选数字个数,从1开始[1...m],r代表组合数字的个数 */void combine3(int m, int r){    int *a = new int[r];    memset(a, 0, r * sizeof(int));     a[0] = 1;    int i = 0;     while (1)    {        // 达到规模,输出结果        if (a[i] – i = r – 1)         {             for (int t = 0; t < r; t++)             {                 cout [color]