回溯算法-学习

最近因为想看看算法..所以学习了一下基本的算法,回溯是一类非常重要的算法,从理论上说,任何问题都可以用回溯解决,呵呵,有点过了..其实回溯的应用还是非常典型的,在利用回溯求解之前,先考虑一下问题的求解是不是很多,而且可以用求解树来表示解空间..

 

不多说了..一般回溯都用到DFS(深度遍历)

而且对于回溯有个固定的模式:

 

 

{
(1)判断是否到了底层，是则返回上一层;
   (2)否则对各种可能情况进行循环：
   {
   if possible
      加入标记;
      进入下一层; //递归调用

      清除标记;
   else
      if 所有情况列举完毕，则返回上一层
   }
}

例如:

输入正整数t、n，以及n个正整数(单调非递增)。
n问题：若n个数中存在某几个数的和是t，则输出这些加法表达式(表达式不重复输出) ；若无解，则输出“NONE”。

Input:
4 7 4 4 3 2 2 1 1

output:
Sums of 4:
4
3+1
2+2
2+1+1

那么:n寻找t的和式，n个数，每个数取或不取，伪代码：

findsum(计算sum,判断第i个数) {
        if (i==n) return; //到达最后一个数的后面

        newsum=sum-第i个数; //取了i层数据

        if (newsum<0) return; //返回上一层,回溯
        if (newsum==0) 输出结果;
        else{ 标记取了第i个数;
            findsum(计算newsum, 判断第(i+1)个数);
        }
        清除第i个数的标记;
        findsum(计算sum,判断第(i+1)个数); //不取i层数据,递归下一层
  }


这里,利用t值减去选中的数,最后测试结果是否为0..