笔试题之回溯法求数组中和为t的组合

// combine.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
#include
#include
#include
using namespace std;

int b[]={5,5,8,9,3,4,6,7,2,1};

int result[100],index=-1;
int T[100];
void output(int b[],int n)
{
 //vector a(b,b+n+1);
 cout< for(int i=0;i<=index;i++)
  cout< //copy(a.begin(),a.end(),ostream_iterator(cout," "));
}

 

//回溯法,两个retreat ，两个advance
void combine(int a[],int n,int t)
{
 while(n>=0)
 { 
   while(n>=0)
   {
    if(t>a[n])     //a[n]能选则选,
    {     
     //入栈(t值和下标)
     index++;   
     result[index]=n;
     T[index]  =t;

     t-=a[n];
     n--;
    }else if(t==a[n]){
     //入栈(t值和下标)
     index++;   
     result[index]=n;
     T[index]  =t;

     output(result,index);

     n=result[index];  
     n--;     
     t=T[index];
     index--;    
     //cout<    }else{
     n--;      //不能选就跳过
    }
   }
 
   while(n<0 && index>=0)
   {
    n=result[index];  //退栈
    n--;     //跳过,可能跳到-1哦
    t=T[index];
    index--;    //出栈
   }
 }
}

 

 

void combine1(int a[],int n,int t)
{

 //cout< if(n<0)
  return;
 if(a[n]  result[++index]=a[n];
  combine(a,n-1,t-a[n]);  //前进的力量
  index--;
 }else if(t==a[n]){
  result[++index]=a[n];
  output(result,index);
  index--;
 }
 combine(a,n-1,t);
}

int _tmain(int argc, _TCHAR* argv[])
{
 sort(b,b+10);

 vector a(b,b+10);
 copy(a.begin(),a.end(),ostream_iterator(cout," "));

 combine(b,9,9);
 getchar();
 return 0;
}