from functools import lru_cache TARGET = DIGITS = '' OPS = ['+', '-', '*', '/'] @lru_cache(maxsize=None) def generate_all_expressions(s): results = dict() # val -> set of expr strings if s.isdigit(): val = int(s) results[val] = {s} for i in range(1, len(s)): left = s[:i] right = s[i:] left_exprs = generate_all_expressions(left) right_exprs = generate_all_expressions(right) for lv, lexprs in left_exprs.items(): for rv, rexprs in right_exprs.items(): for op in OPS: if op == '/' and rv == 0: continue if op == '/' and lv % rv != 0: continue if op == '+': val = lv + rv elif op == '-': val = lv - rv elif op == '*': val = lv * rv elif op == '/': val = lv // rv for le in lexprs: for re in rexprs: expr = f'({le}{op}{re})' if val not in results: results[val] = set() results[val].add(expr) return results def main(): exprs = generate_all_expressions(DIGITS) if TARGET in exprs: print(f'Found: {next(iter(exprs[TARGET]))} = {TARGET}') else: print("No expression found") if __name__ == '__main__': main()
TARGETに数字を、 DIGITS=''の間に12345や65789などの数字を