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

using namespace std;

int a[] = {5, 3, 4, 7};
int memo[3][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;
}

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

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

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

int main(){
    for(int i = 0; i < 3; 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;

    cout << " count combination sum " << combinationSum(7) << endl;

    return 0;
}