Dynamic Programming Example

subsetsum.py

'''
How many ways can the set of numbers from 1 to N be partitioned into two
subsets in such a way that the sum of both subsets is equal?

Hint 1. For each partitioning, the sum of each subset will be the same value

Hint 2. This value is the sum from 1 to N divided by 2. (N * (N + 1) / 2) / 2

Hint 3. The problem has been reduced to, "How many subsets of a given set sum
to a specific value?". Note that once we have this number of subsets, we 
divide it by 2, because each subset is a member of pair that satisfies the
original question.

Hint 4. Start with a Dynamic Programming array that holds the number of subsets
that sum to values from 0 to T, where T is the target value as computed above.
The indicies of the array will be target sums and the values are the number
of subsets that sum to these values.

Hint 5. Add numbers to the set one at a time, updating the DP array with the 
current count for each target

Hint 6. After adding all of the elements to the set the answer will be the
count for the target value
'''

# Solution

import sys

def num_subsets_with_sum(s, target):
    dp = [0 for i in xrange(0, target + 1)]
    dp[0] = 1

    for num in s:
        for curr_target in xrange(target, num - 1, -1):
            if (dp[curr_target - num]):
                dp[curr_target] += dp[curr_target - num]

    return dp[target]

def main():
    n = int(sys.stdin.readline())

    s = set([i for i in xrange(1, n + 1)])
    series_sum = n * (n + 1) / 2
    if series_sum % 2 == 1:
        print 0
        sys.exit(0)
    target = series_sum / 2

    print num_subsets_with_sum(s, target) / 2

if __name__ == "__main__":
    main()

'''
Example:

Given the set {1, 2, 3, 4, 5, 6, 7}, how many ways are there to produce the sum 14?

Technique:
Build up the set one element at a time, while updating a DP array

Number of ways to produce the sum:
0   1   2   3   4   5   6   7   8   9  10  11  12  13  14

1   0   0   0   0   0   0   0   0   0   0   0   0   0   0  (initial DP array)
1   1   0   0   0   0   0   0   0   0   0   0   0   0   0  (iteration 1: add 1 to the set)
1   1   1   1   0   0   0   0   0   0   0   0   0   0   0  (iteration 2: add 2 to the set)
1   1   1   2   1   1   1   0   0   0   0   0   0   0   0  (iteration 3: add 3 to the set)
1   1   1   2   2   2   2   2   1   1   1   0   0   0   0  (iteration 4: add 4 to the set)
1   1   1   2   2   3   3   3   3   3   3   2   2   1   1  (iteration 5: add 5 to the set)
1   1   1   2   2   3   4   4   4   5   5   5   5   4   4  (iteration 6: add 6 to the set)
1   1   1   2   2   3   4   5   5   6   7   7   8   8   8  (iteration 7: add 7 to the set)

In each iteration, previous values of the DP array are used to calculate new values,
given the item being added to the set.
'''