Skip to content

Instantly share code, notes, and snippets.

@mrjoes
Created May 8, 2015 19:17
Show Gist options
  • Save mrjoes/f7d6eb48732bbfe67f9c to your computer and use it in GitHub Desktop.
Save mrjoes/f7d6eb48732bbfe67f9c to your computer and use it in GitHub Desktop.
# Recursively check all combinations with +-
def check(step, acc, ops, digits):
if step >= len(digits):
if acc == 100:
row = ''
for pair in zip(digits, ops):
row += '%s %s ' % pair
print '%s%s' % (row, digits[-1])
else:
check(step + 1, acc + digits[step], ops + ['+'], digits)
check(step + 1, acc - digits[step], ops + ['-'], digits)
# Generate all possible numbers
def calc(digit, s):
acc = 0
for n in xrange(digit, 10):
# Accumulate 1, 12, 123, 1234 based on a current digit
acc = acc * 10 + n
# Store number in a history
history = s + [acc]
# Recursively process all combinations
calc(n + 1, history)
# Check results
if s:
check(1, s[0], [], s)
if __name__ == '__main__':
calc(1, [])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment