回溯法是一种既带有系统性又带有跳跃性的搜索法，它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。

例1、从N个自然数(1,2,…,n)中选出r个数的所有组合。
算法分析：设这r个数为a1,a2,…ar,把它们从大到小排列，则满足：
（1） a1>a2>…>ar;
（2） 其中第i位数(1<=ir-i;
我们按以上原则先确定第一个数，再逐位生成所有的r个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值……按此规则不断循环搜索，直到找出r个数的组合，这种求解方法就是回溯法。
如果按以上方法生成了第i位数ai，下一步的的处理为：
（1） 若ai>r-i且i=r，则输出这r个数并改变ai的值:ai=ai-1;
（2） 若ai>r-i且i≠r，则继续生成下一位ai+1=ai-1;
（3） 若air-1则重复：
若a[i]>r-i，①若i=r，则输出解，并且a[i]:=a[i]-1;
②若i<>r，则继续生成下一位：a[i+1]:=a[i]-1; i:=i+1;
若 a[i] 第三步：结束；
程序实现：

{ TODO : 从N个自然数(1,2,…,n)中选出r个数的所有组合 }
procedure main1;
var n,r,i,j:integer;
    a:array[1..10] of integer;
begin
begin
  readln(n,r);i:=1;a[1]:=n;
  repeat
    if  a[i]>r-i  then {符合条件 }
      if i=r  then     {输出}
      begin
        for j:=1 to r do write(a[j]:3);
        writeln;
        a[i]:=a[i]-1;
      end
      else             {继续搜索}
      begin
        a[i+1]:=a[i]-1;
        i:=i+1;
      end
    else                {回溯}
    begin
      i:=i-1;
      a[i]:=a[i]-1;
    end;
  until  a[1]=r-1;
end;

end;

下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。
例2 数的划分（noip2001tg）
问题描述 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入：n，k (6<n<=200，2<=k<=6)
输出：一个整数，即不同的分法。
样例
输入： 7 3
输出：4 {四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;}
算法分析：此题可以用回溯法求解，设自然数n拆分为a1,a2,…,ak,必须满足以下两个条件：
（1） n=a1+a2+…+ak ；
（2） a1<=a2<=… 现假设己求得的拆分数为a1,a2,…ai,且都满足以上两个条件,设sum=n-a1-a2-…-ai,我们根据不同的情形进行处理：
（1） 如果i=k,则得到一个解，则计数器t加1，并回溯到上一步，改变ai-1的值；
（2） 如果i=ai,则添加下一个元素ai+1；
（3） 如果i<k且sum<ai,则说明达不到目标，回溯到上一步，改变ai-1的值；
算法实现步骤如下：
第一步：输入自然数n,k并初始化；t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k;
第二步：如果a[1]=a[i]则继续搜索；
②若sum<a[i]则回溯；
搜索时，inc(i);a[i]:=a[i-1];sum:=sum-a[i];
回溯时，dec(i); inc(a[i]); sum:=sum+a[i+1]-1;
第三步：输出。
程序如下：

{ TODO : 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序) }
procedure main2;
var
  n,nk,sum,i,k:integer;
  t:longint;
  a:array[1..6] of integer;
begin
  readln(n,k);
  nk:=n div k;
  t:=0; i:=1; a[i]:=1; sum:=n-1;{初始化}
  repeat
    if i=k then                {判断是否搜索到底}
    begin                      {回溯}
      inc(t);
      dec(i);
      inc(a[i]);
      sum:=sum+a[i+1]-1;
    end
    else
    begin
      if sum>=a[i] then         {判断是否回溯}
      begin                     {继续搜}
        inc(i);
        a[i]:=a[i-1];
        sum:=sum-a[i];
      end
      else
      begin                     {回溯}
        dec(i);
        inc(a[i]);
        sum:=sum+a[i+1]-1;
      end;
    end;
  until a[1]>nk;
  writeln(t);
end;