Number of Positive Solutions to a1X1 + a2X2 + ... + anXn = M

Question

Given 2 positive integers n, M and n positive integers a1, a2, ..., an. Count number of positive integer solutions: a1X1 + a2X2 + ... + anXn = M.

Please help me, I'm not sure where I'm going wrong. Here is my code:

#include <bits/stdc++.h>

using namespace std;

int n, m;
int res = 0;
int f = 0, p = 0;  // f = Sum(ai*Xi): (1<=i<=k-1); p = Sum(ai): (k+1<=i<=n)
// f is the remaining part after subtracting the part under consideration, p is the part to ensure that each unexamined element is >= 1.
int m0;     // m0 is max of x[k]; m0=(m-f-p)/ak
const int MAXN = 100;
int A[MAXN], x[MAXN];

void Try(int k)
{
    if (k == n)   
    {
        if ((m0-f) % A[k] == 0)  
        {
            x[k] = (m0-f) / A[k];
            res++;
        }
        return;
    }
    m0 = (m - f - p) / A[k];
    if (m0 >= 1)
        for (int v = 1; v <= m0; v++)
        {
            x[k] = v;
            f=f+A[k]*v;
            p=p-A[k+1];
            Try(k + 1);
            f=f-A[k]*v;
            p=p+A[k+1];
        }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = 2; i <= n; i++)
        p += A[i];
    Try(1);
    cout << res << endl;
    return 0;
}

When I run it, my output is missing some solutions. But if I use the array u[] instead of m0, it has extra solutions.

Answer 1

Thank you, guys, I have fixed my mistake.

#include <bits/stdc++.h>

using namespace std;

int n, m;
int res = 0;
int f = 0, p = 0; 
const int MAXN = 100;
int A[MAXN], x[MAXN];
int u[MAXN]; 

void Try(int k)
{
    u[k] = (m - f - p);
    if (k == n)   
    {
        if (u[k] % A[k] == 0) 
        {
            x[k] = u[k] / A[k];
            res++;
        }
        return;
    }
    if (u[k] >= 1)
        for (int v = 1; v <= u[k]/A[k]; v++)
        {
            x[k] = v;
            f=f+A[k]*v;
            p=p-A[k+1];
            Try(k + 1);
            f=f-A[k]*v;
            p=p+A[k+1];
        }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = 2; i <= n; i++)
        p += A[i];
    Try(1);
    cout << res << endl;
    return 0;
}