[Back Tracking] 복면산

https://www.acmicpc.net/problem/15811

import sys
input=sys.stdin.readline
from itertools import permutations

cnt=0

def to_int(rev, DICT):
    value=0
    for i in range(len(rev)):
        value+=DICT[rev[i]]*(10**i)
    return value

def promising(i, n, D, s1, s2, s3):
    if i==0:
        return True
    a=to_int(s1, D)
    b=to_int(s2, D)
    c=to_int(s3, D)
    M=10**i
    return (a+b)%M == c%M


def backtrack(i, n, D, r1, r2, r3):
    global cnt
    if promising(i, n, D, r1[:i], r2[:i], r3[:i]):
        if i>n:
            print("YES")
            #print(D, "YES")
            #cnt+=1
            #return
            exit(0)
        else:
            letters=ith_letters(i, r1, r2, r3, D)
            digits=set(range(10)) - set(D.values())
            for perm in permutations(digits, len(letters)):
                for k, v in zip(letters, perm):
                    D[k]=v
                backtrack(i+1, n, D, r1, r2, r3)
                for k in letters:
                    D.pop(k)

def ith_letters(i, r1, r2, r3, D):
    s=""
    if i<len(r1):
        s+=r1[i]
    if i<len(r2):
        s+=r2[i]
    if i<len(r3):
        s+=r3[i]
    return set(s)-set(D.keys())

def solve(r1, r2, r3):
    n=max(len(r1), len(r2), len(r3))
    backtrack(0, n, {}, r1, r2, r3)
    print("NO")

w1, w2, w3 =input().split()
solve(w1[::-1], w2[::-1], w3[::-1])
#print("---------------------------------")
#print("the total answer is .. ", cnt)

# 복면산의 해답들 출력
# 복면산의 해답 조합의 개수 출력
import sys
input=sys.stdin.readline
from itertools import permutations

cnt=0

def to_int(rev, DICT):
    value=0
    for i in range(len(rev)):
        value+=DICT[rev[i]]*(10**i)
    return value

def promising(i, n, D, s1, s2, s3):
    if i==0:
        return True
    a=to_int(s1, D)
    b=to_int(s2, D)
    c=to_int(s3, D)
    M=10**i
    return (a+b)%M == c%M


def backtrack(i, n, D, r1, r2, r3):
    global cnt
    if promising(i, n, D, r1[:i], r2[:i], r3[:i]):
        if i>n:
            print(D, "YES")
            cnt+=1
            return
            #exit(0)
        else:
            letters=ith_letters(i, r1, r2, r3, D)
            digits=set(range(10)) - set(D.values())
            for perm in permutations(digits, len(letters)):
                for k, v in zip(letters, perm):
                    D[k]=v
                backtrack(i+1, n, D, r1, r2, r3)
                for k in letters:
                    D.pop(k)

def ith_letters(i, r1, r2, r3, D):
    s=""
    if i<len(r1):
        s+=r1[i]
    if i<len(r2):
        s+=r2[i]
    if i<len(r3):
        s+=r3[i]
    return set(s)-set(D.keys())

def solve(r1, r2, r3):
    n=max(len(r1), len(r2), len(r3))
    backtrack(0, n, {}, r1, r2, r3)
    print("NO")

w1, w2, w3 =input().split()
solve(w1[::-1], w2[::-1], w3[::-1])
print("---------------------------------")
print("the total answer is .. ", cnt)