StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let <code>A</code> be the input array. I'll assume it is sorted ascending.</p> <pre><code>A = [2,3,6,8,11] </code></pre> <p>Let <code>M[i]</code> be the number of sublist found <strong>so far</strong> to have sum equal to <code>i</code>.</p> <p>Starts with only <code>M[0] = 1</code> because there is one list with has sum equals zero, that is the empty list.</p> <pre><code>M = [1,0,0,...] </code></pre> <p>Then take each item from the list <code>A</code> one-by-one. Update the number of ways you have to compose a list of each sum when considering that the item you just take can be used.</p> <pre><code>Suppose a is the new item for each j: if M[j] != 0: M_next[j+a] = M[j+a] + M[j] </code></pre> <p>When you found any <code>M[j]</code> which reach 10 during that, you should stop the algorithm. Also, modify to remember the items in the list to be able to get the actual list at the end!</p> <p>Notes:</p> <ul> <li>You can use <em>sparse</em> representation for <code>M</code></li> <li>This is similar to those Knapsack and subset sum problems. Perhaps you might find many better algorithms reading on those.</li> </ul> <hr> <p>Here is a working code in Python:</p> <pre><code>A = [2,3,6,8,11] t = sum(A) M = [0]*(t+1) M[0] = 1 print 'init M :',M for a in A: for j in range(len(M)-1,-1,-1): if M[j] != 0: M[j+a] += M[j] print 'use',a,':',M </code></pre> <p>And its output:</p> <pre><code>init M : [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] use 2 : [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] use 3 : [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] use 6 : [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] use 8 : [1, 0, 1, 1, 0, 1, 1, 0, 2, 1, 1, 2, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] use 11 : [1, 0, 1, 1, 0, 1, 1, 0, 2, 1, 1, 3, 0, 2, 2, 0, 2, 2, 0, 3, 1, 1, 2, 0, 1, 1, 0, 1, 1, 0, 1] </code></pre> <p>Take the interpretation of <code>M[11] = 3</code> at the end for example; it means there are 3 sublists with sum equals 11. If you trace the progress, you can see the sublists are <code>{2,3,6},{3,8},{11}</code>.</p> <hr> <p>To account for the fact that you allow the 10 sublists to have <em>similar</em> sum. Not just exactly the same sum. You might want to change termination condition from "terminate if any M[j] >= 10" to "terminate if sum(M[j:j+3]) >= 10" or something like that.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload