编程之美-快速寻找满足条件的2个数（扩展问题）

原题是：

   能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值？

   这个可以将数组排序，然后前后各一个指针向中间靠拢寻找。

扩展问题1：

   如果将问题中的“两个数字”改成“三个数字”或“任意个数字时”，你的解答时什么？

 

   写了一段代码，查找一个集合中是否存在一个子集，其中数字之和等于给定的值(given),有则返回子集，没有就返回空。

 

#include <iostream>
using namespace std;

int FindSubset(int* arr,int sum,int*include,int n)
{
 int curr=0;
 int tmp_sum=0;
 
 while(curr>=0)
 {
  if(0==include[curr])
  {
   include[curr]=1;
   tmp_sum += arr[curr];
   if(tmp_sum==sum)
    return 1;
   else if(tmp_sum>sum)
   {
    include[curr]=0;
    tmp_sum -= arr[curr];
   }
   curr++;
  }
  if(curr>n-1)
  {
   while(1==include[curr-1])
   {
    curr--;
    include[curr]=0;
    tmp_sum -= arr[curr];
    if(curr<1)
     return 0;
   }
   while(0==include[curr-1])
   {
    curr--;
    if(curr<1)
     return 0;
   }
   include[curr-1]=0;
   tmp_sum -= arr[curr-1]; 
  }
 }
 return 0;
}

 

int main()
{
 int arr[]={1,2,4,6,3,7,97,46,32,25,12,11};
 int n;
 int target=112;

 n=sizeof(arr)/sizeof(arr[0]);

 int *include = new int[n];
 memset(include,0,n*sizeof(int));

 if(FindSubset(arr,target,include,n))
 {
  for(int i=0;i<n;i++)
  {
   if(include[i])
    cout<<arr[i]<<" ";
  }
 }
 else
 {
  cout<<"Find no subset"<<endl;
 }
 cout<<endl;
 return 0;
}