Subset sum

题目描述

给定一个全是正整数的array， 和一个targe值。 你可以取任意数目的elements from the array，允许有重复，然后使得这些elements的和等于target 问一共多少种solutions？

解题方法

The subset sum problem for n can be divided into 2 subproblems:

1. include the last element, recur for n = n-1, sum = sum - set[n-1]
2. exclude the last element, recur for n = n - 1

n is the number of elements in the set

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || 
                           isSubsetSum(arr, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0

recursive

it would try all the subsets

DP

• time complexity O(sum * n)

Solution

recursive

def isSubsetSum(set, sum):
    if not sum:
        return True
    if not n and sum:
        return False
    if set[-1] > sum:
        return isSubsetSum(set[:-1], sum)

    return isSubsetSum(set[:-1], sum) or isSubsetSum(set[:-1], sum-set[-1])

DP

• create a 2d table dp[i][j]
• fill in bottom up manner
• dp[i][j] == True if set[:j] sum to i
• follow the same routine

def isSubsetSum(set, sum):
    dp = [[False for i in range(len(set)+1)] for j in range(sum+1)]

    ##init status
    for i in range(len(set)+1):
        dp[0][i] = True

    for j in range(sum+1):
        dp[j][0] = False

    for i in range(1, sum+1):
        for j in range(1, len(set)+1):
            dp[i][j] = dp[i][j-1]
            if set[j-1] <= i:
                dp[i][j] = dp[i][j-1] or dp[i-set[j-1]][j-1]

    return dp[sum][len(set)]

Reference