def calc(numbers, symbols):
    result = numbers[0]
    total = len(symbols)
    idx_symbol = 0
    while idx_symbol < total:
        current_symbol = symbols[idx_symbol]
        tmp = numbers[idx_symbol+1]
        try:
            next_symbol = symbols[idx_symbol+1]
        except IndexError:
            next_symbol = '/'
        if next_symbol == '*':
            idx_symbol = idx_symbol + 1
            while True:
                tmp = tmp * numbers[idx_symbol+1]
                idx_symbol = idx_symbol + 1
                if idx_symbol == total or symbols[idx_symbol] != '*':
                    break
        else:
            idx_symbol = idx_symbol + 1
        if current_symbol == '+':
            result = result + tmp
        elif current_symbol == '-':
            result = result - tmp
        elif current_symbol == '*':
            assert result == numbers[0]
            result = result * tmp
    return result


def format(sn, symbols):
    assert '/' not in symbols
    return ''.join(n+s for n, s in zip(sn, symbols)) + sn[-1]


def find(sn, target):
    numbers = [int(n) for n in sn]
    if len(sn) == 1:
        if numbers[0] == target:
            return sn
        else:
            return []
    symbols = ['/'] * (len(numbers) - 1)
    stop = len(symbols) - 1
    result = []

    def loop(n, symbols):
        for symbol in '+-*':
            symbols[n] = symbol
            if n == stop:
                if (calc(numbers, symbols) == target):
                    result.append(format(sn, symbols))
            else:
                loop(n+1, symbols)

    loop(0, symbols)
    return result


def combination(sn):
    result = [[sn[0]]]
    for item in sn[1:]:
        new_result = []
        for r in result:
            new_list = r.copy()
            new_list.append(item)
            new_result.append(new_list)
            new_list = r
            if new_list[-1] != '0':
                new_list[-1] = new_list[-1] + item
                new_result.append(new_list)
        result = new_result
    return result


def find_all(sn, target):
    result = []
    for s in combination(sn):
        r = find(s, target)
        if r:
            result.extend(r)
    return result


def findall(numbers, target):
    result = []
    total = len(numbers)

    def dfs(start, s, r, last):
        assert start > 0
        if start == total:
            if r == target:
                result.append(s)
            return
        for end in range(start+1, total+1):
            sn = numbers[start:end]
            n = int(sn)
            dfs(end, f'{s}+{sn}', r+n, n)
            dfs(end, f'{s}-{sn}', r-n, -n)
            dfs(end, f'{s}*{sn}', r-last+n*last, last*n)
            if sn == '0':
                return

    for end in range(1, total+1):
        sn = numbers[:end]
        n = int(sn)
        dfs(end, sn, n, n)
        if sn == '0':
            break

    return result


if __name__ == '__main__':
    # print(findall('232', 8))
    # print(findall('123', 6))
    # print(findall('105', 5))
    # print(findall('00', 0))
    # print(findall('3456237490', 9191))
    print(findall('1', 1))
