假设写成 X + Y = Z
X, Y, Z满足
len(X) >= len(Y),
len(Z) = len(X) 或 len(X)+1
从最低位开始，一位一位填X和Y,那么Z相应位置就能算出来了。
import random
# generate random digits
N = random.randint(3,16)
S = [0]*N
count = [0]*10
for i in range(0,N):
S[i] = random.randint(1,9)
count[S[i]] += 1
print S
L = [[0, 0, 0]]*N
P = [0]*N
W = [0]*3
# X + Y = Z
# X, Y, Z are of length W[0], W[1], W[2]
# with W[0] >= W[1] and W[2] = W[0] or W[0]+1
# try to fill in the k'th bit
def fill(L, count, W, k, carry):
# terminate when X is full
if k == W[0]:
if carry == 0:
# no carry, W[2] should equal W[0]
if W[2] == W[0]:
return 1
else:
return 0
else:
# with carry, W[2]=W[0]+1 and with a '1' left
if W[2] == W[0] +1 and count[1] == 1:
L[k] = [0, 0, 1]
return 1
else:
return 0
for x in range(0,10):
if count[x]:
count[x] -= 1
if W[1] > k:
# when Y is not full
for y in range(0, 10):
if y==0 and k == W[1]-1:
continue
if count[y]:
count[y] -= 1
z = (x + y + carry)%10
new_carry = (x + y + carry)/10
if count[z]:
count[z] -= 1
L[k] = [x, y, z]
if fill(L, count, W, k+1, new_carry):
return 1
count[z] += 1
count[y] += 1
else:
# when Y is full
z = (x + carry)%10
new_carry = (x + carry)/10
if count[z]:
count[z] -= 1
L[k] = [x, 0, z]
if fill(L, count, W, k+1, new_carry):
return 1
count[z] += 1
count[x] += 1
found = 0
for W[0] in range( (N+1)/3, (N-1)/2+1 ):
for W[2] in range(W[0], W[0]+2):
W[1] = N - W[2] - W[0]
if W[1] >= 1 and W[1] <= W[0]:
if fill(L, count, W, 0, 0):
found = 1
break
if found:
break
if found:
for i in range(W[0]-1, -1, -1):
print L[i][0],
print ' + ',
for i in range(W[1]-1, -1, -1):
print L[i][1],
print ' = ',
for i in range(W[2]-1, -1, -1):
print L[i][2],
print
else:
print 'no solution'
