Return elements of array in subset sum problem

user_6094930 0
Viewed 2071

For the following recursive solution to the subset sum problem (see this link), the following code returns true if there is any subset in a whose sum equals the value of sum 

def isSubsetSum(set,n, sum) : 

    # Base Cases 
    if (sum == 0) : 
        return True
    if (n == 0 and sum != 0) : 
        return False

    # If last element is greater than sum, then ignore it 
    if (set[n - 1] > sum) : 
        return isSubsetSum(set, n - 1, sum); 

    # else, check if sum can be obtained by any of the following 
    # (a) including the last element 
    # (b) excluding the last element    
    return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1]) 

set = [2, 1, 14, 12, 15, 2] 
sum = 9
n = len(set) 
if (isSubsetSum(set, n, sum) == True) : 
    print("Found a subset with given sum") 
else : 
    print("No subset with given sum")

How could I also return the indices of a which satisfy the sum?

Also, how can I make the function work for negative integers in array a.

dynamic-programming numpy python
3 Answers

This is one possibility:

def isSubsetSum(numbers, n, x, indices):
    # Base Cases
    if (x == 0):
        return True
    if (n == 0 and x != 0):
        return False
    # If last element is greater than x, then ignore it
    if (numbers[n - 1] > x):
        return isSubsetSum(numbers, n - 1, x, indices)
    # else, check if x can be obtained by any of the following
    # (a) including the last element
    found = isSubsetSum(numbers, n - 1, x, indices)
    if found: return True
    # (b) excluding the last element
    indices.insert(0, n - 1)
    found = isSubsetSum(numbers, n - 1, x - numbers[n - 1], indices)
    if not found: indices.pop(0)
    return found

numbers = [2, 1, 4, 12, 15, 3]
x = 9
n = len(numbers)
indices = []
found = isSubsetSum(numbers, n, x, indices)
print(found)
# True
print(indices)
# [0, 2, 5]

EDIT: For a cleaner interface, you can wrap the previous function in another one that returns the list of indices on success and None otherwise:

def isSubsetSum(numbers, x):
    indices = []
    found = _isSubsetSum_rec(numbers, len(numbers), x, indices)
    return indices if found else None

def _isSubsetSum_rec(numbers, n, x, indices):
    # Previous function
user_17827920

Here's an approach: Instead of True and False we return the subarray if found, else None:

def isSubsetSum(sset,n, ssum) : 

    # Base Cases 
    if (ssum == 0) : 
        return []
    # not found
    if (n == 0 and ssum != 0) : 
        return None

    # If last element is greater than sum, then ignore it 
    if (sset[n - 1] > ssum) : 
        return isSubsetSum(sset, n - 1, ssum); 

    # else, check if sum can be obtained by any of the following 
    # (a) including the last element 
    # (b) excluding the last element    
    a1 = isSubsetSum(sset, n-1, ssum)

    # (b) excluding last element fails
    if a1 is None:
        a2 = isSubsetSum(sset, n-1, ssum-sset[n-1])

        # (a) including last element fails
        if a2 is None:
            return None

        # (a) including last element successes
        else: return a2 + [sset[n-1]]
    else:
        return a1


sset = [2, 1, 4, 12, 15, 2] 
ssum = 9
n = len(sset) 
subset = isSubsetSum(sset, n, ssum) 
if subset is not None : 
    print(subset) 
else : 
    print("No subset with given sum") 

# [2, 1, 4, 2]
user_42384080

The "easy" way is to make the index list another parameter to the function. Maintain it as you move down the call tree.

The "clean" way is to build it as you return back up the tree with a successful result. Instead of returning a Boolean, return a list of the indices; None indicates failure.

One important note: do not "shadow" a built-in type with a variable name; set is both dangerous as a variable name and misleading. Try coins, for example.

Base cases:

if (sum == 0) : 
    return [n]
if (n == 0 and sum != 0) : 
    return None

Recursion:

include = isSubsetSum(coins, n-1, sum-coins[n-1]):
if include:
    return include.append(n-1)

Those are immediate additions for your existing code. I strongly recommend that you research this problem on line to see how others have solved it. You waste space and time by passing the entire list and a pointer as parameters; rather, you can start with the last element and work your way back, snipping the end off the list on each call. This will make your indexing problems much simpler.

user_47851850
Related