suppose we have n1, n2. n2 is n1 without one digit
e.g. n1 = 123, then n2 can be 12, 13 or 23.
Now given N = n1 + n2, output all the possible combinations.
Call the numbers A and B. B is A with one digit missing.
We can write:
A = 10^(k+1) X + 10^k Z + Y
B = 10^k X + Y
where Y < 10^k, Z < 10.
Now look at N % 10.
- If it is odd, and k > 0, then
N % 10 = (A+B) % 10 = 2Ycontradiction. Hence, k = 0, and A = 10X + Z, B = X. In the equation N = 11X + Z, we can try Z = N % 11, and if Z != 10 then there is the only solution X = (N - Z) / 11.
- If it is even, then we know the last digit of Y up to two choices. For example, if N = 102, then Y%10 is either 1 or 6. If it is 1, then we want to solve the same problem for N = 10 and append 1 to the answers. If it is 6, then we want to solve the same problem for N = (102 - 12) / 10 = 9 and append 6 to the answer.
def solve(N): if N == 0: return [(0, 0)] r = N % 10 if r % 2: Z = N % 11 if Z != 10: X = (N - Z) / 11 return [(10 * X + Z, X)] else: choices = [x for x in xrange(10) if 2 * x % 10 == r] ans =  for choice in choices: N2 = (N - 2 * choice) / 10 for A, B in solve(N2): ans.append((10 * A + choice, 10 * B + choice)) return ans
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.