c++ - Recursive backtracking -

i having problem backtracking function loops data can't write here whole program code can put here function.

bool sharemoney(int quantity, int *values, int index, int moneya, int half, bool *ifchosen) {      if(moneya == half)         return true;     else if(index >= quantity)         return false;      moneya += values[index];      if(sharemoney(quantity, values,index+1, moneya, half, ifchosen))     {         ifchosen[index] = true;         return true;     };      moneya -= values[index];      if(sharemoney(quantity, values,index+1, moneya, half, ifchosen))     {         ifchosen[index] = false;         return true;     };      return false; } 

now here explanation:

quantity - number of elements in values array
values - array of numbers
index - variable control recursion
moneya - variable stores sum of element array values
half - number moneya should reach after recursion done
ifchosen - array of boolean elements refers array values

the function gets quantity of elements lenght of values array, values array numbers in it's sorted highest lowest one, index controls recursion , default it's 0 starts first element, moneya variable stores numbers values array , should reach half half of numbers sumed values array , ifchosen stores numbers chosen.

the whole function this, sums elements values array , checks wether reached half if it's lower half adds moneya , mark in ifchosen goes next one, if sum higher half gets , unmark in ifchosen array , substract moneya. should highest elements.

here simple example:

6 - number of elements 50, 20, 19, 15, 2, 2 - elements stored in values array total sum - 108 half of elements - 54 

the result 1 should be:

50, 2, 2 - marked true in ifchosen 20, 19, 15 - marked false in ifchosen  

of course simple example great job more complicated have more numbers , 1 number occurs more once loops , recursion never stops. i've been working on 1.5 weeks , asked friends nobody knows wrong it. know has bit knapsack problem didn't have 1 yet , still have study.

i'm looking forward answer help.

i'm sorry punctuation i'm here first time , didn't got used formatting.

here got 1 example:

89 86 83 67 53 45 5 1      44 43 34 33 33 24 23 23 23 22 21 21 19 12 11 9 8 7 5 3 2 2 2 1 1 1 1 1       real    0m28.007s      user    0m27.926s      sys 0m0.028s 

now 1 think loops forever: 43 elements:

12 2 2 1 3 4 5 6 7 89 33 12 45 23 44 23 11 44 1 3 5 7 88 33 8 19 43 22 86 5 34 23 21 67 83 24 21 53 9 11 34 1 1 

@karl bielefeldt yes know there many combinations that's why trying speed up. got gives me wrong results input. can make correct, works faster before ?

bool sharemoney(int quantity, int *values, int index, int moneya, int half, bool *ifchosen){  if(index>=quantity && moneya == half){ return true;} else if(index>=quantity) return false;  moneya+=values[index]; ifchosen[index]=true;  if(moneya<=half){            sharemoney(quantity,values,index+1,moneya, half,ifchosen);     if(moneya==half) return true;      return true; }else{     sharemoney(quantity,values,index+1,moneya, half,ifchosen);           moneya-=values[index];     ifchosen[index]=false;      return true; }   return false;} 

the typical way cut down on number of iterations on problem calculate bound on subtree solving linear program (like problem, remaining variables allowed take on fractional values). simplex solves linear program in approximately quadratic time instead of exponential. best solution linear program @ least best integer or binary solution same constraints, if linear solution worse current best, can throw away whole subtree without exhaustive evaluation.

edit: let's start simplifying brute force algorithm:

int* sharemoney( int pool_size, int *pool, int *solution, int cumsum, int goal) {     if (cumsum == goal) return solution; #if prune_above     if (cumsum > goal) return 0; #endif     if (!pool_size) return 0;  #if prune_below     int max = cumsum;     for( int n = pool_size; n--; max += pool[n] );     if (max < goal) return 0; #endif      int* subproblem = sharemoney(pool_size-1, pool+1, solution, cumsum, goal);     if (subproblem) return subproblem;      *solution = *pool;     return sharemoney(pool_size-1, pool+1, solution+1, cumsum+*pool, goal); } 

after execution, solution contains list of values used reach goal, , returned pointer indicates end of list.

the conditional blocks first suggested improvement. no recursion necessary in these cases.

we can eliminate need iterate calculate max @ each step:

int* sharemoney( int pool_size, int *pool, int *solution, int cumsum, int poolsum, int goal) {     if (cumsum == goal) return solution; #if prune_above     if (cumsum > goal) return 0; #endif     if (!pool_size) return 0;  #if prune_below     if (cumsum + poolsum < goal) return 0; #endif      int* subproblem = sharemoney(pool_size-1, pool+1, solution, cumsum, poolsum - *pool, goal);     if (subproblem) return subproblem;      *solution = *pool;     return sharemoney(pool_size-1, pool+1, solution+1, cumsum+*pool, poolsum - *pool, goal); } 

here's function solve integer version (better repeated coin denominations):

int* sharemoney( int pool_size, int *pool_denom, int *pool_cardinality, int *solution, int cumsum, int poolsum, int goal) {     if (cumsum == goal) return solution; #if prune_above     if (cumsum > goal) return 0; #endif     if (!pool_size) return 0;  #if prune_below     if (cumsum + poolsum < goal) return 0; #endif      poolsum -= *pool_cardinality * *pool_denom;     (*solution = *pool_cardinality; *solution >= 0; --*solution) {         int* subproblem = sharemoney(pool_size-1, pool_denom+1, pool_cardinality+1, solution+1, cumsum + *solution * *pool_denom, poolsum, goal);         if (subproblem) return subproblem;     }      return 0; } 

instead of getting straight list of individual coins, takes list of denominations, , number of available coins of each one. result number of coins of each denomination needed solution.