This was an interesting problem, so I decided to solve it . Forgive the C-style pointers everywhere . If you don't understand how it works, ask me.
Code:
#include <iostream>
const int LIST_DELIMITER = 0; // cannot be in the list, else the printing gets messed up
bool sumPossible(int* data, int* answers, int listSize, int target) {
if (data[0] == target) {
answers[0] = data[0];
return true;
}
for (int i = 1; i < listSize; i++) {
if (sumPossible(data + i, answers, listSize - i, target)) return true; // data[0] not included in list of answers
answers[0] = data[0];
if (sumPossible(data + i, answers + 1, listSize - i, target - data[i])) return true; // data[0] included in list
}
return false;
}
void clearList(int* data, int num) {
for (int i = 0; i < num; i++) data[i] = LIST_DELIMITER;
}
void printList(int* data, int num) {
for (int i = 0; i < num; i++) {
if (data[i] == LIST_DELIMITER) return;
std::cout << '\t' << data[i];
}
}
int main(int argc, char *argv[])
{
int list[] = {2 , 3 ,4 ,5};
int answers[] = {LIST_DELIMITER, LIST_DELIMITER, LIST_DELIMITER, LIST_DELIMITER};
int listSize = 4;
for (int i = 0; i < 20; i++) {
bool itWorked = sumPossible(list, answers, listSize, i);
std::cout << "Target " << i << '\t' << itWorked;
if (itWorked) {
printList(answers, listSize);
}
clearList(answers, listSize);
std::cout << std::endl;
}
char wait; std::cin >> wait;
return 0;
}