Getting combinations back from memoized subset-sum algorithm?
<p>I've been working on a pretty basic subset sum problem. Given a sum (say, s=6) and the numbers ((1:s), so, [1,2,3,4,5]), I
had to find the total number of combinations that totalled s (so: [1,5], [2,4], [1,2,3]). It was quite easy to satisify the
requirements of the problem by doing a brute-force approach. For my own learning, I've been trying to understand how I can instead implement a memoizable algorithm that would allow me to calculate combinations for very large values of n (say, 500). Obviously, the brute-force approach becomes untenable quickly for values over 70 or so.</p>

<p>Digging around on the internet quite a bit, I already found an algorithm <a href="http://www.markandclick.com/advance.html#SubsetSum" rel="nofollow">here</a> that works quite well. This is the code I'm currently working with:</p>

<pre><code>def get_combos_wrapped():
    cache = {}
    def get_combos(numbers, idx, total, depth=0, which=''):
        dstr = '\t' * depth
        print("%scalled: idx=%s, total=%s %s" % (dstr, idx, total, which))
        if (idx, total) in cache:
          # print("cache hit: %s, %s" % (idx, total))
          to_return = cache[(idx, total)]
          del(cache[(idx, total)])
          return to_return
        depth += 1
        if idx &gt;= len(numbers):
          to_return = 1 if total == 0 else 0
          print("%sreturning %s" % (dstr, to_return))
          return to_return
        the_sum =   get_combos(numbers, idx + 1, total, depth) \
                  + get_combos(numbers, idx + 1, total - numbers[idx], depth)
        print("%sreturning %s" % (dstr, the_sum))
        cache[(idx, total)] = the_sum
        return the_sum
    return get_combos
</code></pre>

<p>Here's my problem... The algorithm  is still completely mysterious to me -- I just know that it returns the right totals. I'm wondering if anyone can indulge my ignorance and offer insight into understanding 1) how this works, and 2) whether I would be able to use this algorithm to actually get back the unique number combinations given a value of s. The following is some output I hacked together to help me visualize the program flow for s=6, though unfortunately it hasn't really helped. Thank you very much for your help.</p>

<pre><code>called: idx=0, total=6 
        called: idx=1, total=6 
                called: idx=2, total=6 
                        called: idx=3, total=6 
                                called: idx=4, total=6 
                                        called: idx=5, total=6 
                                        returning 0
                                        called: idx=5, total=1 
                                        returning 0
                                returning 0
                                called: idx=4, total=2 
                                        called: idx=5, total=2 
                                        returning 0
                                        called: idx=5, total=-3 
                                        returning 0
                                returning 0
                        returning 0
                        called: idx=3, total=3 
                                called: idx=4, total=3 
                                        called: idx=5, total=3 
                                        returning 0
                                        called: idx=5, total=-2 
                                        returning 0
                                returning 0
                                called: idx=4, total=-1 
                                        called: idx=5, total=-1 
                                        returning 0
                                        called: idx=5, total=-6 
                                        returning 0
                                returning 0
                        returning 0
                returning 0
                called: idx=2, total=4 
                        called: idx=3, total=4 
                                called: idx=4, total=4 
                                        called: idx=5, total=4 
                                        returning 0
                                        called: idx=5, total=-1 
                                        returning 0
                                returning 0
                                called: idx=4, total=0 
                                        called: idx=5, total=0 
                                        returning 1
                                        called: idx=5, total=-5 
                                        returning 0
                                returning 1
                        returning 1
                        called: idx=3, total=1 
                                called: idx=4, total=1 
                                        called: idx=5, total=1 
                                        returning 0
                                        called: idx=5, total=-4 
                                        returning 0
                                returning 0
                                called: idx=4, total=-3 
                                        called: idx=5, total=-3 
                                        returning 0
                                        called: idx=5, total=-8 
                                        returning 0
                                returning 0
                        returning 0
                returning 1
        returning 1
        called: idx=1, total=5 
                called: idx=2, total=5 
                        called: idx=3, total=5 
                                called: idx=4, total=5 
                                        called: idx=5, total=5 
                                        returning 0
                                        called: idx=5, total=0 
                                        returning 1
                                returning 1
                                called: idx=4, total=1 
                        returning 1
                        called: idx=3, total=2 
                                called: idx=4, total=2 
                                called: idx=4, total=-2 
                                        called: idx=5, total=-2 
                                        returning 0
                                        called: idx=5, total=-7 
                                        returning 0
                                returning 0
                        returning 0
                returning 1
                called: idx=2, total=3 
                        called: idx=3, total=3 
                        called: idx=3, total=0 
                                called: idx=4, total=0 
                                called: idx=4, total=-4 
                                        called: idx=5, total=-4 
                                        returning 0
                                        called: idx=5, total=-9 
                                        returning 0
                                returning 0
                        returning 1
                returning 1
        returning 2
returning 3
3
</code></pre>

<p>You may simplify your problem using <a href="https://docs.python.org/2/library/itertools.html#itertools.combinations" rel="nofollow"><code>itertools.combinations()</code></a> as:</p>

<pre><code>&gt;&gt;&gt; from itertools import combinations
&gt;&gt;&gt; s = 6
&gt;&gt;&gt; my_list = range(1, s)
# Value of 'my_list':
# [1, 2, 3, 4, 5]

&gt;&gt;&gt; my_combinations = [combinations(my_list, i) for i in range(2, s)]
# Value of 'my_combinations' (in actual will be containg &lt;combinations&gt; objects):
# [[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)], [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)], [(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5)], [(1, 2, 3, 4, 5)]]

&gt;&gt;&gt; my_required_set = [my_set for my_sublist in my_combinations for my_set in my_sublist if sum(my_set) == s]
&gt;&gt;&gt; my_required_set
[(1, 5), (2, 4), (1, 2, 3)]
</code></pre>

python algorithm memoization subset-sum