Print all the combination from a candidate set that sum to a target value

Problem: Given a target set of integers (may contain negative integers) and a target value, print all the combinations that sum to the target value. Each element can only be used once in a combination. For the same combination, only print once.

• Example:  candidate set [-1, 3, 2, 1, 5], target value 4. Then we can have 1+3, -1+2+3

Solution: Recursion is used to solve this problem. Also first sort the candidate set.

• Assume we have a prev_sum (the sum of the previous integers we had added up) and current integer we want to add, if prev_sum + current integer > target value, we return.
• if prev_sum + current integer = target value, we print out the combination and also return. No need to explore further, since the candidate set is sorted.
• if prev_sum + current integer < target value, we take the current integer, update prev_sum, and also update an array that is used to track the combination, then we make a recursive function call
• an array, int index[] is used to track the integers we had used.  The advantage of this array is simplicity. Definitely we can use STL vectors.
• If the target value is negative, taking the above approach naively will have some problem (see chunjie's comment below). There are different ways to handle this case. One way used below is to convert the target value into positive and also convert the whole set of integers by multiplying with a "-1".

The related code is as follow:

void print_comb(int index[], int n, vector<int> set, int negative)
{
   for(int i =0; i<=n; i++)
     cout << (negative * set[index[i]]) << ((i<n)?'+':' ');
     cout << endl;
}

//assume a sorted list
void _print_all_combine_n(int target, int negative, int n_prev, int index[], vector<int> set, int pos, int n)
{

   for(int i = pos; i < set.size(); i++)
   {
     if(n_prev + set[i] == target) 
      {
         index[n] = i;
         print_comb(index, n, set, negative);
         return;
      }
      
      // we don't need to look at later cases, since they are not possible
      if(n_prev + set[i] > target)        
            return;

      // skip duplicate numbers before advancing, since we only use each number once
      int m = i+1;
      while(set[m] == set[i] && m < set.size())
           m++;
      i = m-1;

      if(n_prev + set[i] < target)
      {
         index[n] = i;
         print_all_combine_n(target, n_prev+set[i], index, set, i+1, n+1);

      }

   }

}

//assume a sorted list
void print_all_combine_n(int target)
{

   int index[10000];
   index[0] = 0;
   vector<int> set(myints, myints + sizeof(myints) / sizeof(int) );
   
   int negative = 1;

   if(target < 0) 
   {
      for(int i=0; i<set.size(); i++)
         set[i] = (-1)*set[i];

      negative = -1;
   }

   sort(set.begin(), set.end());

   print_all_combine_n(target * negative, negative, 0, index, set, 0, 0);
}

int main()
{

   int myints[] = {10, 1, 2, 7, 6, 1, 5, -3};

   
   print_all_combine_n(8);

}