#include<iostream>
#define N int(sizeof(a) / sizeof(a[0]))

using namespace std;

int a[] = {5, 3, 4, 7};
int memo[2][10000];

bool canSum(int n){
    if(memo[0][n] != -1) return memo[0][n];

    if(n == 0) {
        memo[0][n] = 1;
        return true;
    }
    if(n < 0) {
        memo[0][n] = 0;
        return false;
    }

    for(int i = 0; i < N; i++){
        int ost = n - a[i];
        bool res = canSum(ost);
        if(res == true){
            memo[0][n] = 1;
            return true;
        }
    }
    memo[0][n] = 0;
    return false;
}

int howManySum(int n){
    if(memo[1][n] != -1) return memo[1][n];

    if(n == 0){
        memo[1][n] = 1;
        return 1;
    }
    if(n < 0){
       memo[1][n] = 0;
       return 0;
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
        int ost = n - a[i];
        ans = ans + howManySum(ost);
    }
    memo[1][n] = ans;
    return ans;
}

void combinationSum(int n, string s){
    if(n == 0){
        cout << "combination = " << s << endl;
        return;
    }
    if(n < 0){
       return;
    }


    for(int i = 0; i < N; i++){
        int ost = n - a[i];
        char num[2] = {a[i] + '0', '\0'};
        string ns = s + num + " ";
        combinationSum(ost, ns);
    }
}

int main(){
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 10000; j++){
                memo[i][j] = -1;
        }
    }

    cout << "can sum " << canSum(7) << endl;

    cout << "count how many sum " << howManySum(7) << endl;

    combinationSum(7, "");

    return 0;
}