Python solution without using a recursion. This solves the problem in O(N*F*M) time where N is size of array, F is number of possible operations, and M is the target multiplier (101). Edit: the bound is actually tighter if M is prime. It can solve in O(M**2*F + N) time.

The idea is simple. You need to keep the cache to memorize all the values reachable in mod 101.

1. Put the first elemen of the array in the cache. (Along with the string representation.)
2. Loop the array one element at a time.
3. Apply the each operations (+, -, *) to the values in the cache and the current element, and store the new value mod 101 in the new cache. (With the formula)
4. If you get 0, get the formula and the current index i, and return the formula with '*X_{i+1}*X_{i+2}...X_{N}' appended in the end.

For example:
A = [30, 70, 1, 3]
cache = {30: '30'}

Iteration 1:
val = 70
30 + 70 mod 101 = 100
30 - 70 mod 101 = 61
30 * 70 mod 101 = 80
cache = {
61: '30-70',
100: '30+70',
80: '30*70'}

Iteration 2:
61 + 1 mod 101 = 62
61 - 1 mod 101 = 60
61 * 1 mod 101 = 61
100 + 1 mod 101 = 0
-- quit iteration --
(formula = '30+70+1' index = 3)
return '30+70+1' + '*3'

#!/bin/python3

import sys

S = ('+', lambda x, y: x + y)
D = ('-', lambda x, y: x - y + 101)
M = ('*', lambda x, y: x * y)
func = [S, D, M]

def arithmeticExpressions(arr):
    form, index = _ae(arr)
    remain = len(arr) - index
    extra = zip(['*'] * remain, arr[-remain:])
    extra_s = ''.join([o + str(n) for o, n in extra])
    return form + extra_s

def _ae(arr):
    cache = {}
    first = arr[0]
    cache[first] = str(first)
    for index, n in enumerate(arr[1:]):
        next_cache = {}
        for val in cache:
            for name, f in func:
                next_val = f(val, n) % 101
                next_form = cache[val] + name + str(n)
                if next_val == 0:
                    return next_form, index + 2
                next_cache[next_val] = next_form
        cache = next_cache

if __name__ == "__main__":
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    result = arithmeticExpressions(arr)
    print(result)