Python Fast and Elegant Solution Beats 90%

• ``````class Solution(object):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
n = len(num)
if n == 0: return []
ans = []
# Step 2: compose [digit] into a validated string
def compose(arr):
total = len(arr)
def collect(i, pre, val):
if i >= total:
if val == target: ans.append(pre.lstrip('+'))
else:
collect(i+1, pre+"+"+str(arr[i]), val + arr[i])
if i > 0: collect(i+1, pre+"-"+str(arr[i]), val - arr[i])
product = arr[i]
candidates = []
s = str(arr[i])
for j in range(i+1, total):
product *= arr[j]
s += '*'+str(arr[j])
candidates.append((j+1, s, product))
for c in candidates:
collect(c[0], pre + '+' + c[1], c[2]+val)
if i>0: collect(c[0], pre + '-' + c[1], -c[2]+val)
collect(0, '', 0)

# Step 1: decompose num into [digit]
def decompose(i, curr):
if i >= n: compose(curr)
else:
if num[i] == '0': decompose(i+1, curr + [0])
else:
for j in range(i+1, n+1):
decompose(j, curr + [int(num[i:j])])

decompose(0, [])
return ans``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.