<h3>TL;DR: <a href="https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/" rel="nofollow noreferrer">easiest algorithm is here</a>, most efficient algorithm is explained below.</h3>
<p>When you restrict the coefficients to positive integers, this problem is NP-complete (as long as <code>len</code> is part of the input and not fixed). So a truly <em>efficient</em> solution isn't going to happen. (It's called the Unbounded Subset Sum Problem, if you want to google around; <a href="https://folk.idi.ntnu.no/mlh/algkon/hard.pdf" rel="nofollow noreferrer">a proof of its hardness is here</a>.)</p>
<p><a href="https://arxiv.org/pdf/1610.04712.pdf" rel="nofollow noreferrer">The most efficient algorithm I've found is from this paper</a>:</p>
<p><a href="https://i.stack.imgur.com/wgqo0.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wgqo0.png" alt="algorithm in pseudocode" /></a></p>
<p>The ⊕<sub>t</sub> operation is a &quot;capped sumset&quot;, also described in the paper: it basically operates like this (sketched in Python):</p>
<pre><code>def capped_sumset(a, b, t): # a, b sets of naturals, t natural
    a0 = a | {0}
    b0 = b | {0}
    return {
        x+y
            for x in a0
            for y in b0
        if x+y &lt;= t
    }
</code></pre>
<p>The hardest part about implementing this in C is going to be all the set operations; once you have a good implementation of sets of integers, the algorithm itself isn't too bad.</p>
<p>If you don't care about efficiency, of course, you can use the &quot;classic dynamic program&quot; mentioned in the base case of the algorithm; <a href="https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/" rel="nofollow noreferrer">you can find a detailed explanation with examples in several programming languages here</a>. But be prepared for an exponential running time!</p>
Check if an integer can be represented as a linear combination of integers in array
<p>I'm trying to solve a problem where given an integer <code>n</code>, and an array of integers <code>a</code> -- can <code>n</code> be represented as a linear combination of elements from <code>a</code> such that the coefficients are <strong>positive</strong> integers as well.</p>

<p>I saw <a href="https://stackoverflow.com/questions/47583925/c-check-if-an-integer-is-linear-combination-of-elements-in-an-array">C: check if an integer is linear combination of elements in an array</a> and implemented it as such in C, but it doesn't work in all cases.</p>

<pre class="lang-c prettyprint-override"><code>int gcd(int a, int b) {
  if (a == 0) {
    return b;
  }
  return gcd(b % a, a);
}

bool can_be_changed(const int a[], int len, int val) {
  for (int i = 0; i &lt; len - 1; i++) {
    for (int j = i + 1; j &lt; len; j++) {
      if (val % gcd(a[i], a[j]) == 0) {
        return true;
      }
    }
  }
  return false;
}

</code></pre>

<p>But, if <code>a = {4,5,6}</code> and <code>val=7</code> the code will return true as <code>gcd(4,5) = 1</code> and <code>7 % gcd(4,5) == 0</code> will evaluate to <code>true</code> thus returning <code>true</code> which it shouldn't.</p>

<p>Any help is appreciated, thanks!</p>