python script to exhaustively search for partitions of "123456789" and their negatives that sum to 100

puzzle.py

#!/usr/bin/python

import itertools

def pairwise_combine(array):
	for i in xrange(len(array)-1):
		arr = array[:i] + [''.join(array[i:i+2])] + array[i+2:]
		yield arr

array = [j for j in "123456789"]
options = {tuple(array)}
def run(array):
	if len(array) in [1,2]:
		pass
	else:
		for combo in pairwise_combine(array):
			options.add(tuple(combo))
			run(combo)

def gen_signs(length):
	signs = set()
	for i in itertools.combinations_with_replacement('+-',length):
		for j in itertools.permutations(i):
			signs.add(j)
	return signs

run(array)
for opt in options:
	signs = gen_signs(len(opt))
	for sign in signs:
		zipped = zip(sign,opt)
		numbers = [''.join(i) for i in zipped]
		numbers,
		if sum([int(i) for i in numbers]) == 100:
			answer = ' '.join(numbers).strip('+')
			operations = answer.count('+') + answer.count('-')
			print "%s, with %d operations"%(answer,operations)