回溯法其實也是一種搜索算法，它可以方便的搜索解空間。
回溯法解題通常可以從以下三步入手：
1、針對問題，定義解空間
2、確定易于搜索的解空間結構
3、以深度優先的方式搜索解空間，并在搜索的過程中進行剪枝
回溯法通常在解空間樹上進行搜索，而解空間樹通常有子集樹和排列樹。
針對這兩個問題，算法的框架基本如下：
用回溯法搜索子集合樹的一般框架：

      void backtrack(int t){
  if(t > n) output(x);
  else{
    for(int i = f(n,t); i <= g(n,t);i++){
          x[t] = h(i);
          if(constraint(t) && bound(t)) backtrack(t+1);
     }
  }
}

    

用回溯法搜索排列樹的算法框架：

      void backtrack(int t){
  if(t > n) output(x);
  else{
    for(int i = f(n,t); i <= g(n,t);i++){
          swap(x[t],x[i]);
          if(constraint(t) && bound(t)) backtrack(t+1);
          swap(x[t],x[i]); 
    }
  }
}

    

其中f(n,t),g(n,t)表示當前擴展結點處未搜索過的子樹的起始標號和終止標號,
h(i)表示當前擴展節點處，x[t]第i個可選值。constraint(t)和bound(t)是當前
擴展結點處的約束函數和限界函數。constraint(t)返回true時，在當前擴展結點
x[1:t]取值滿足約束條件，否則不滿足約束條件，可減去相應的子樹。bound(t)返
回的值為true時，在當前擴展結點x[1:x]處取值未使目標函數越界，還需要由backtrack(t+1)
對其相應的子樹進一步搜索。
用回溯法其實質上是提供了搜索解空間的方法，當我們能夠搜遍解空間時，
顯然我們就能夠找到最優的或者滿足條件的解。這便是可行性的問題， 而效率可以
通過剪枝函數來降低。但事實上一旦解空間的結構確定了，很大程度上時間復雜度
也就確定了，所以選擇易于搜索的解空間很重要。
下面我們看看兩個最簡單的回溯問題，他們也代表了兩種搜索類型的問題：子集合問題和
排列問題。
第一個問題：
求集合s的所有子集(不包括空集),我們可以按照第一個框架來寫代碼：

      #include<iostream>
using namespace std;

int s[3] = {1,3,6};
int x[3];
int  N = 3;
void print(){
   for(int j = 0; j < N; j++)
	if(x[j] == 1)
	   cout << s[j] << " ";
   cout << endl;
}

void subset(int i){
 	if(i >= N){
        print();
	    return;
	}

	x[i] = 1;//搜索右子樹
	subset(i+1);
	x[i] = 0;//搜索左子樹
	subset(i+1);
}

int main(){
  subset(0);
  return 0;
}

    

下面我們看第二個問題：排列的問題，求一個集合元素的全排列。
我們可以按照第二個框架寫出代碼：

      #include<iostream>
using namespace std;

int a[4] = {1,2,3,4};
const int N = 4;

void print(){
	for(int i = 0; i < N; i++)
		   cout << a[i] << " ";
    cout << endl;
}

void swap(int *a,int i,int j){
  int temp;
  temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

void backtrack(int i){
	if(i >= N){
		print();
	}
	for(int j = i; j < N; j++){
		swap(a,i,j);
		backtrack(i+1);
		swap(a,i,j);
	}
}

int main(){
  backtrack(0);
  return 0;
}

    

這兩個問題很有代表性，事實上有許多問題都是從這兩個問題演變而來的。第一個問題，它窮舉了所有問題的子集，這是所有第一種類型的基礎，第二個問題,它給出了窮舉所有排列的方法，這是所有的第二種類型的問題的基礎。理解這兩個問題,是回溯算法的基礎.
下面看看一個較簡單的問題：
整數集合s和一個整數sum，求集合s的所有子集su,使得su的元素之和為sum。
這個問題很顯然是個子集合問題，我們很容易就可以把第一段代碼修改成這個問題的代碼：

      int sum = 10;
int r = 0;
int s[5] = {1,3,6,4,2};
int x[5];
int  N = 5;

void print(){
   for(int j = 0; j < N; j++)
	if(x[j] == 1)
	   cout << s[j] << " ";
   cout << endl;
}
void sumSet(int i){
	if(i >= N){
		if(sum == r) print();
	    return;
	}
	if(r < sum){//搜索右子樹
	  r += s[i];
	  x[i] = 1;
	  sumSet(i+1);
	  r -= s[i]; 
	}
	x[i] = 0;//搜索左子樹
	sumSet(i+1);
}

int main(){
  sumSet(0);
  return 0;
}