Converting subset sum algorithm from JavaScript to Python

Question

I have the following code in JavaScript to compute the minimum elements in array whose sum equals n:

function findMinSum(arr, n){
    if(!arr) return 
    let min 
    for (let i=0; i<arr.length; i++) {

        /* if a number equals the sum, it's obviously
         * the shortest set, just return it
         */
        if (arr[i] == n) return [arr[i]]     

        /* recursively call on subset with
         * sum adjusted for removed element 
         */
        let next = findMinSum(arr.slice(i+1), n-arr[i])

        /* we only care about next if it's shorter then 
         * the shortest thing we've seen so far
         */
        if (next){
            if(min === undefined || next.length < min.length){
                min = [arr[i], ...next]
            }
        }
    }
    return min && min  /* if we found a match return it, otherwise return undefined */
}

I got this code from here.

I wanted to convert it to Python, so I did the following:

def findMinSum(arr, n):
    if not arr:
        return

    min = []
    min_len = len(min)
    for i in range(0, len(arr)):

        if(arr[i] == n):
            return (arr[i])

        next = []
        next = findMinSum(arr[i+1:], n-arr[i])

        if(next == list):
            next_len = len(next)
        else:
            next_len = next

        if(next):
            print(next) # printing next for debugging purpose 
            if( ( not min ) or (next_len < min_len) ):
                min = [ next, arr[i]]

    return min

arr = [8, 6, 1, 5, 9, 3]
get_min = findMinSum(arr, 14)

print(get_min)

But when I run this code, I get the following error:

3
[3, 1]
9
[[3, 1], 6]
3
[3, 9]
Traceback (most recent call last):
  File "test1.py", line 34, in <module>
    min2 = findMinSum(arr, 14)
  File "test1.py", line 25, in findMinSum
    if( ( not min ) or (next_len < min_len) ):
TypeError: '<' not supported between instances of 'list' and 'int'

The expected output should be [8, 6] or [9, 5].

I can't think of any other way to write the code as I'm a newbie to Python. Also I don't want to import any other module except numpy.

Where did I go wrong with this translation?

Welcome to SO! What's `list` in `if(next == list):`? Recommend not using `list` `next` or other builtin variable names. Also, skip `()`s in Python for conditionals and return values. You might accidentally make tuples. — ggorlen, Dec 08 '19 at 16:23
@ggorlen Thankyou! I'm checking whether next is a list or not. Also, I tried changing the variable names still I'm getting the same output. — kc314, Dec 08 '19 at 16:28
That doesn't work then--you want `isinstance` or `type` here. Yeah, `next` is an iterator function, so I'm just writing a general comment, not a solution. Caching `len` calls is also bad practice, and this might be the cause: `min_len = len(min)`. This never gets updated when `min` changes. `min` also overwrites the builtin function `min`. — ggorlen, Dec 08 '19 at 16:31
@ggorlen Thanks for the suggestions, I'll try implementing them in my code. — kc314, Dec 08 '19 at 16:47
@ggorlen sorry, the sum should be 14, thanks for pointing out — kc314, Dec 08 '19 at 16:51

ggorlen · Accepted Answer · 2019-12-08T17:13:42.323

There are a variety of issues here.

Never overwrite builtins. Python defines min, next and list. If you overwrite them, you may run into very subtle bugs.
Python doesn't have arrays, it has lists. Never cache calls to len--this code doesn't update min_len = len(min), so the value is stale in future comparisons in this loop if min is ever updated.
Avoid unnecessary parentheses around conditionals and return statements since parenthesis are used for creating tuples. return (arr[i]) should be return [arr[i]] (a single element list).
min = [ next, arr[i]] doesn't match [arr[i], ...next] either in ordering or unpacking/spreading. Use min = [arr[i], *next] to flatten next.
JS and Python treat undefined/None and boolean array/list values differently. JS treats an empty array as truthy but Python treats empty lists as falsey. min = [] doesn't capture the original JS code which sets min = undefined implicitly, so if not min checks both whether min is null or empty, which is not comparable to the original JS version.
No need to check types; checking for None or not None is sufficient.
if (next) { if (more stuff ... can just be one block using and. No reason to nest (this is a problem in the original).
Use enumerate instead of range to iterate over a list in most cases (if you do use range, range(0, len(some_list)) can be range(len(some_list)).
Adhere to PEP-8. Use snake_case for function and variable names.

Here's my re-write:

def find_smallest_sum(lst, n):
    if not lst:
        return None

    smallest = None

    for i, e in enumerate(lst):
        if e == n:
            return [e]

        next_lst = find_smallest_sum(lst[i+1:], n - e)

        if next_lst is not None and (smallest is None or len(next_lst) < len(smallest)):
            smallest = [e, *next_lst]

    return smallest

if __name__ == "__main__":
    print(find_smallest_sum([10, 0, -1, 20, 25, 30], 59))  # => [10, -1, 20, 30]
    print(find_smallest_sum([8, 6, 1, 5, 9, 3], 14))       # => [5, 9]

Converting subset sum algorithm from JavaScript to Python

1 Answers1