试题:找出数组中元素和为指定值的所有组合

本问题来自论坛, 题意大概如下:

指定一个数组, 和一个数值, 找出数组中元素和为这个指定数值的所有组合

如指定数组元素为[1, 2, 3], 而指定数值为6, 则满足要求的组合为:{1, 2}, {3}

#include <iostream>
using namespace std;

void solve(int n, int data[], int start, int end,
           int used[], int index, int size, bool change)
{
    if (0 == n && change) {
        for (int i = 0; i <= index; ++i) {
            cout << used[i] << " ";
        }
        cout << endl;
    }
    // cause zero may in the data array, we cannot jump out now
    if (start < end && index < size - 1) {
		if (n >= data[start]) {
			++index;
			used[index] = data[start];
			solve(n - data[start], data, start + 1, end, used, index, size, true);
			--index;
		}
		solve(n, data, start + 1, end, used, index, size, false);
    }
}

void solve(int n, int data[], int used[], int size)
{
    solve(n, data, 0, size, used, -1, size, false);
}

int main()
{
	{
		cout << "------ block 1 ------" << endl;
		int n = 15;
		int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
		int used[10]= {0};
		solve(n, data, used, 10);
	}

	{
		cout << "------ block 2 ------" << endl;
		int n = 15;
		int data[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
		int used[10]= {0};
		solve(n, data, used, 10);
	}

    return 0;
}