Sport Prog Sum

#include <iostream>
#include <string.h>

using namespace std;

#define N 4
#define X 7

int nums[] = {5, 3, 4, 7};

bool canSum(int x, int* nums, int n, int i) {
    if (x == 0) return true;
    if (x < 0 || i >= n) return false;

    for (int k = 0; k <= x / nums[i]; k++)
        if (canSum(x - k * nums[i], nums, n, i + 1))
            return true;
    return false;
}

int howManySum(int x, int* nums, int n, int i) {
    if (x == 0) return 1;
    if (x < 0 || i >= n) return 0;

    int sum = 0;
    for (int k = 0; k <= x / nums[i]; k++)
        sum += howManySum(x - k * nums[i], nums, n, i + 1);
    return sum;
}

void combinationSum(int x, int* nums, int n, int i, int* comb, int s) {
    if (x == 0) {
        cout << "combination: ";
        for (int i = 0; i < s - 1; i++)
            cout << comb[i] << " + ";
        cout << comb[s - 1] << endl;
        return;
    }
    if (x < 0 || i >= n) return;

    for (int k = 0; k <= x / nums[i]; k++) {
        if (k) comb[s++] = nums[i];
        combinationSum(x - k * nums[i], nums, n, i + 1, comb, s);
    }
}

int getMin(int arr[], int n) {
    int min = arr[0];

    for (int i = 1; i < n; i++)
        if (min > arr[i]) min = arr[i];
    return min;
}

int main() {

    cout << "canSum = " << canSum(X, nums, N, 0) << endl;

    cout << "howManySum = " << howManySum(X, nums, N, 0) << endl;

    int comb[X / getMin(nums, N) + 1];

    combinationSum(X, nums, N, 0, comb, 0);

    return 0;
}