Arithmetic Expressions

  • + 0 comments

    Despite this problem being in the category "Recursion", I feel it much more appropriate to use DP.

    Here what that looks like in Python3:

    def arithmeticExpressions(arr):
        this = [None] * 101
        this[arr[0]] = [arr[0]]
        for a in arr[1:]:
            if this[0]:
                this[0] += ['*', a]
            else:
                that = [None] * 101
                for i, v in enumerate(this):
                    if v is not None:
                        that[(i+a)%101] = this[i] + ['+', a]
                        that[(i-a)%101] = this[i] + ['-', a]
                        that[(i*a)%101] = this[i] + ['*', a]
                this = that
        return ''.join(map(str, this[0]))