Thread: A recursive problem

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;
}