Reconstruct bitsequence from a Set of properties

This is a small knapsack problem.

Here is a solution in Python with iterators. The reason for iterators is that the number of answers can be very large. For example there are 15029 bitsequences that add up to 100 of length 20. And that grows exponentially.

# Finds all answers and puts it in an compact but complex data structure.
def find_subsum_path_tree(target, array):
    # For each value, we will have an array of trees of how to get there.
    # The simplest tree is the empty sum, None
    paths_to = {0: [None]}
    for val in array:
        new_paths_to = {}
        for key, prev_paths in paths_to.iteritems():
            # Take care of initialization.
            if key not in new_paths_to:
                new_paths_to[key] = []
            if key + val not in new_paths_to:
                new_paths_to[key + val] = []

            # We have ways to get to key without using val
            new_paths_to[key] = new_paths_to[key] + prev_paths
            # We have ways to get to key+val with using val.
            #
            # NOTE: our data structure here will look like:
            #     [
            #         prev_tree_1,
            #         prev_tree_2,
            #         ...
            #         prev_tree_n,
            #         [val, [
            #             prev_path_1,
            #             prev_path_2,
            #             ...
            #             prev_path_m
            #         ]]
            #    ]
            #
            # This encodes a lot of options.  In data structures that get
            # reused.  So there can be a lot of paths, but this is not a
            # lot of data.
            new_paths_to[key + val] = new_paths_to[key + val] + [[val, prev_paths]]
        paths_to = new_paths_to
    if target in paths_to:
        return paths_to[target]
    else:
        return []

# Turn the complex tree into arrays recursively.
# With iterators so it doesn't live in memory all at once.    
def subsum_paths(target, array):
    tree = find_subsum_path_tree(target, array)

    def path_decode(subtree):
        if subtree[0] is None:
            yield []
        else:
            for option in subtree:
                value, rest = option
                for subpath in path_decode(rest):
                    yield [value] + subpath

    for path in path_decode(tree):
        yield path

# Use the previous knapsack solution to find bitsequences as desired.
def bitsequences(target, length):
    for path in subsum_paths(target, range(1, length + 1)):
        bits = ['0' for _ in range(length)]
        for n in path:
            bits[length - n] = '1'
        yield "".join(bits)

# And a demonstration of how to use this code.    
for sequence in bitsequences(15, 8):
    print(sequence)