用回溯法求子集和的c++代碼

　　用回溯算法解決問題的一般步驟為：

　　一、定義一個解空間，它包含問題的解。

　　二、利用适于搜尋的方法組織解空間。

　　三、利用深度優先法搜尋解空間。

　　四、利用限界函數避免移動到不可能産生解的子空間。

　　問題的解空間通常是在搜尋問題的解的過程中動态産生的，這是回溯算法的一個重要特性。

　　回溯法是一個既帶有系統性又帶有跳躍性的的搜尋算法。它在包含問題的所有解的解空間樹中，按照深度優先的政策，從根結點出發搜尋解空間樹。算法搜尋至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜尋，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的政策進行搜尋。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜尋遍才結束。而回溯法在用來求問題的任一解時，隻要搜尋到問題的一個解就可以結束。這種以深度優先的方式系統地搜尋問題的解的算法稱為回溯法，它适用于解一些組合數較大的問題.

 1 回溯算法也叫試探法，它是一種系統地搜尋問題的解的方法。回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。

#include "stdafx.h"

#include "stdio.h"

#include "iostream"

using namespace std;

int backtrack(int arr[],int n,int sum);

struct SUBBUFF

{

 int data;//存放目前的值

 char IsIn;//記錄目前值是否加入了子集

};

int main(int argc, char* argv[])

{

 int n,sum; //定義了集合元素個數，以及要求的子集的和

 cout<<"輸入元素個數:";

 cin>>n;

 cout<<"輸入要求的子集和：";

 cin>>sum;

 SUBBUFF *arr = new SUBBUFF[n];

 int i=0;

 cout<<"初始的集合元素"<<endl;

 for (i=0;i<n;i++)

 {

  cin>>arr[i].data;

  arr[i].IsIn = 'N';//将目前的值的初始化狀态設為 'N',表示不在子集中

 }

 int pointto = 0,countsum = 0;//目前指向的角标，和現在的子集和

 while (pointto>=0)//進入循環，開始回溯

 {

  if (arr[pointto].IsIn == 'N')//向子集裡面增加值

  {

   countsum +=arr[pointto].data;

   arr[pointto].IsIn = 'Y';

   if (countsum == sum)//找到答案，輸出結果

   {

    for (i=0;i<n;i++)

    {

     if (arr[i].IsIn == 'Y')

     {

      printf("%d ",arr[i].data);      

     }

    }

    return 0;

   }

   else

    if (countsum > sum)//開始回溯

    {

     countsum -=arr[pointto].data;

     arr[pointto].IsIn = 'N';

    }

   pointto++;   

  }

  if (pointto >= n)

  {

   while(arr[pointto-1].IsIn == 'Y')//開始回溯

   {

    pointto--;

    countsum -= arr[pointto].data;

    arr[pointto].IsIn = 'N';    

    if (pointto < 1)

    {

     printf("Nosolution!/n");

     return 0;

    }

   }

   while(arr[pointto-1].IsIn == 'N')

   {

    pointto--;

    if (pointto < 1)

    {

     printf("Nosolution!/n");

     return 0;

    }

   }

   arr[pointto-1].IsIn = 'N';

   countsum -= arr[pointto-1].data;

  }

 }

 return 0;

}

//記下來，一面将來忘記了，不知道該怎麼做。