from itertools import permutations

def solve(ns, target):
    if len(ns) == 1 and target == ns[0]:
        return str(ns[0])
    if len(ns) == 2:
        x, y = ns[0], ns[1]
        if x + y == target:
            return (True, f"({x}+{y})")
        elif x > y and x - y == target:
            return (True, f"({x}-{y})")
        elif x < y and y - x == target:
            return (True, f"({y}-{x})")
        elif x * y == target:
            return (True, f"{x}*{y}")
        elif x % y == 0 and x // y == target:
            return (True, f"{x}/{y}")
        elif y % x == 0 and y // x == target:
            return (True, f"{x}/{y}")
        else:
            return (False, '')
    else:
        for n in ns:   
            others = [m for m in ns if m != n]
            b, st = solve(others, target - n)
            if b:
                return (True, f"{n}+{st}")
            b, st = solve(others, target + n)
            if b:
                return (True, f"{st}-({n})")
            if target % n == 0:
                b, st = solve(others, target // n)
                if b:
                    return (True, f"{n}*({st})")
            b, st = solve(others, target * n)
            if b:
                return (True, f"({st})/{n}")
        for n, m in permutations(ns, r=2):
            others = [x for x in ns if x != n and x != m]
            r = n + m
            b, st = solve(others, target - r)
            if b:
                return (True, f"{n}+{m}+{st}")
            b, st = solve(others, target + r)
            if b:
                return (True, f"{st} - ({n}+{m})")
            b, st = solve(others, target * r)
            if b:
                return (True, f"{st} / ({n}+{m})")
            if target % r == 0:
                b, st = solve(others, target // r)
                if b:
                    return (True, f"{st} * ({n}+{m})")
            if n > m:
                r = n - m
                b, st = solve(others, target - r)
                if b:
                    return (True, f"{n}-{m}+{st}")
                b, st = solve(others, target + r)
                if b:
                    return (True, f"{st} - ({n}-{m})")
                b, st = solve(others, target * r)
                if b:
                    return (True, f"{st} / ({n}-{m})")
                if target % r == 0:
                    b, st = solve(others, target // r)
                    if b:
                        return (True, f"{st} * ({n}-{m})")
            r = n * m
            b, st = solve(others, target - r)
            if b:
                return (True, f"{n}*{m}+{st}")
            b, st = solve(others, target + r)
            if b:
                return (True, f"{st} - ({n}*{m})")
            b, st = solve(others, target * r)
            if b:
                return (True, f"{st} / ({n}*{m})")
            if target % r == 0:
                b, st = solve(others, target // r)
                if b:
                    return (True, f"{st} * ({n}*{m})")
            if n % m == 0:
                r = n // m
                b, st = solve(others, target - r)
                if b:
                    return (True, f"{n}/{m}+{st}")
                b, st = solve(others, target + r)
                if b:
                    return (True, f"{st} - ({n}/{m})")
                b, st = solve(others, target * r)
                if b:
                    return (True, f"{st} / ({n}/{m})")
                if target % r == 0:
                    b, st = solve(others, target // r)
                    if b:
                        return (True, f"{st} * ({n}/{m})")
        return (False, '')

from itertools import combinations

def solve_le_compte_est_bon(numbers, target):
    # dp[(tuple_of_indices)] = { value: "string_expression" }
    # We use indices to distinguish between multiple instances of the same number
    dp = {}

    # Initialize with single numbers
    for i, n in enumerate(numbers):
        dp[(i,)] = {n: str(n)}

    # Build up combinations from size 2 to the full length of numbers
    for size in range(2, len(numbers) + 1):
        for left_size in range(1, size // 2 + 1):
            right_size = size - left_size
            
            # Find all ways to split the current 'size' into two groups
            for left_indices in combinations(range(len(numbers)), left_size):
                remaining_indices = [idx for idx in range(len(numbers)) if idx not in left_indices]
                
                for right_indices in combinations(remaining_indices, right_size):
                    # Sort to ensure unique keys in DP
                    combined_key = tuple(sorted(left_indices + right_indices))
                    if combined_key not in dp:
                        dp[combined_key] = {}

                    # Try to combine every result from the left group with the right group
                    for v1, expr1 in dp.get(tuple(sorted(left_indices)), {}).items():
                        for v2, expr2 in dp.get(tuple(sorted(right_indices)), {}).items():
                            
                            # Standard Operations
                            ops = [
                                (v1 + v2, f"({expr1}+{expr2})"),
                                (v1 * v2, f"({expr1}*{expr2})"),
                                (v1 - v2, f"({expr1}-{expr2})"),
                                (v2 - v1, f"({expr2}-{expr1})"),
                            ]
                            if v2 != 0 and v1 % v2 == 0:
                                ops.append((v1 // v2, f"({expr1}/{v2})"))
                            if v1 != 0 and v2 % v1 == 0:
                                ops.append((v2 // v1, f"({expr2}/{v1})"))

                            for res, expr in ops:
                                if res > 0: # The game usually only uses positive integers
                                    dp[combined_key][res] = expr
                                    # If we found the target, we can return early (optional)
                                    if res == target:
                                        return (True, expr)

    return (False, "No solution")

# --- Test Section ---
tests = [
    ([50, 2, 13], 38),
    ([4, 7, 2, 3], 22),
    ([100,75,9,5,8,7],256),
    ([8,5,1,25,75,2], 926),
    ([3,7,9,4,5,1], 885),
    ([1,8,3,7,50,5], 554),
    ([3,4,30], 40),
    ([50,75,25,100,2,5], 212),
    ([100,25,1,4], 651) # No solution!
]

for ns, target in tests:
    found, result = solve_le_compte_est_bon(ns, target)
    print(f"Target {target}: {result}")
    


for ns, target in tests:
    r = solve(ns, target)
    print(r)