回溯法

回溯（backtracking）法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.

例题

写一个在1，2，…，9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。

//例5.4算法
#include <stdio.h>
#define N 9
void fun(char op[],int sum,int prevadd,int a[],int i)
{
	if (i==N)						//扫描完所有位置
	{
		if (sum==100)				//找到一个解
		{
			printf("  %d",a[0]);	//输出解
			for (int j=1;j<N;j++)
			{
				if (op[j]!=' ')
					printf("%c",op[j]);
				printf("%d",a[j]);
			}
			printf("=100\n");
		}
		return;
	}
	op[i]='+';						//位置i插入'+'
	sum+=a[i];						//计算结果
	fun(op,sum,a[i],a,i+1);			//继续处理下一个位置
	sum-=a[i];						//回溯

	op[i]='-';						//位置i插入'-'
	sum-=a[i];						//计算结果
	fun(op,sum,-a[i],a,i+1);		//继续处理下一个位置
	sum+=a[i];						//回溯

	op[i]=' ';						//位置i插入' '
	sum-=prevadd;					//先减去前面的元素值
	int tmp;						//计算新元素值
	if (prevadd>0)
		tmp=prevadd*10+a[i];		//如prevadd=5,a[i]=6,结果为56
	else
		tmp=prevadd*10-a[i];		//如prevadd=-5,a[i]=6,结果为-56
	sum+=tmp;						//计算合并结果
	fun(op,sum,tmp,a,i+1);			//继续处理下一个位置
	sum-=tmp;						//回溯sum
	sum+=prevadd;
}
int main()
{
	int a[N];
	char op[N];					//op[i]表示在位置i插入运算符
	for (int i=0;i<N;i++)		//为a赋值为1,2，...,9
		a[i]=i+1;
	printf("求解结果\n");
	fun(op,a[0],a[0],a,1);		//插入位置i从1开始
}