用回溯法求子集和的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;

}

//记下来，一面将来忘记了，不知道该怎么做。