Given a positive integer
n positive integers x1 , x2 , ... , xn does there exist non negative integers a1 , a2 , ... , an such that:
$$y = a_1 x_1 + a_2 x_2 + \dots + a_n x_n$$
The problem is just to answer if such ai's exist or not.
My approach was to check for a given
yif either of (y - xi) for i in [1..n] is expressible as a linear combination of xi's recursively and base case being that all xi's are expressible. But this approach is too slow for large values of y.
Is there some alternate faster approach?