Making special combinations (C++)

Question

I need some help with a C++ problem. User enters how many numbers he want to enter, then all the numbers and a special value. Program must find and write all the combinations of numbers whose sum equals to the special value. Example:

Input

12
1 5 7 3 10 8 9 2 4 6 11 13
15

Output:

4 11
2 13 
9 6 
9 2 4
3 2 4 6
3 8 4 
3 10 2
7 2 6
7 8 
5 4 6
5 8 2
5 10
5 7 3
1 8 6
1 8 2 4
1 10 4
1 3 11
1 3 9 2
1 7 3 4 
1 5 9
1 5 3 6
1 5 3 2 4
1 5 7 2

Code

Here's the code that writes all the combinations that consist of 2 elements:

#include <iostream> 
using namespace std;

int main(int argc, const char * argv[])
{
    int size;
    cout << "Enter size: ";
    cin >> size;
    int *numbers = new int[size];
    cout << "Enter numbers: ";
    for (int i = 0; i < size; i++)
        cin >> numbers[i];
    int target;
    cout << "Enter target: ";
    cin >> target;
    int sum = 0;
    for (int i = 0; i < size-1; i++)
    {
        for (int j = i+1; j < size; j++)
        {
            sum = numbers[i];
            sum += numbers[j];
            if (sum == target)
                cout << numbers[i] << " " << numbers[j] << "\n";
        }
    }
    return 0;
}

If I replace that for loop with this one, the program will write all the combinations that consist of 3 elements:

for (int i = 0; i < size-2; i++)
{
   for (int j = i+1; j < size-1; j++)
   {
      for (int k = j+1; k < size; k++)
      {
         sum = numbers[i] + numbers[j];
         sum += numbers[k];
         if (sum == target)
         cout << numbers[i] << " " << numbers[j] << " " << numbers[k] << "\n";
       }
    }
}

Here's my question: how to make a program that writes ALL the possible combinations?

Answer 1

1. Take the first number from your list (e.g., 1).
2. Remove this number from your list, as well as deduct it from your "destination" total.
3. Now you have a new list and a new destination total. Repeat.
4. If your total exceeds your destination, skip the current number (i.e., retain the number within the list, don't update the destination) and move to the next.
5. If none of the remaining items in the list let you reach your destination, pop the last number you added to your destination total, and update it with the next number in the list.
6. If you reach your destination total, you have a subset of numbers from your original list (with a size that is anything between 1 and the number of elements in the list) that add up to your intended total.