原题地址(中等)

方法1—分治递归

思路

像这种类型的题，组合情况非常多，循环穷举的话几乎不可能，所以会自然而然的想到分治递归。

我们知道，任何一个中缀表达式，都可以画成二叉树的形状，如果可以随意加括号的话，那么一个表达式就对应多棵二叉树，比如1+2*3的表达式二叉树如下：

我们可以借助这个思路来实现递归。

任意一个表达式，都可以表示为 a op b 的形式， a,b 表示两个子表达式， op 表示运算符。我们可以分而治之，先算出 a 的可能取值，再算出 b 的可能取值，最后组合进行 op 运算。
至于 a ，又可以表示为 a1 op a2 的形式。而递归的终点，就是子表达式中只有数字，即直接返回。

子问题与原问题具有相同的性质，可以通过同一种方式来求解，这就是分治问题的特点。
**
动态规划详解及与分治法的异同

梳理一下：
递归边界：当前表达式（字符串）中只有数字，直接返回含有一个元素的列表
递归算法：
函数可以求出当前表达式的值（可能有多个），用列表返回。
求解表达式的过程为通过递归求解两个子表达式的值，然后进行 op 运算。

代码1（python）

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        if input.isdigit():    # 递归边界
            return [eval(input)]
        rel = []
        for i in range(len(input)):
            if input[i] in "+-*":
                a = self.diffWaysToCompute(input[:i]) 
                b = self.diffWaysToCompute(input[i+1:])
                for num1 in a:
                    for num2 in b:
                        rel.append(eval(str(num1)+input[i]+str(num2)))
        return rel

代码2

不知道为啥，上面代码运行很慢，只超过了5%的朋友，于是乎我进行了一些小的改动，把 eval 函数换掉了。

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        if input.isdigit():
            return [int(input)]

        rel = []
        for i in range(len(input)):
            if input[i] in "+-*":
                a = self.diffWaysToCompute(input[:i])
                b = self.diffWaysToCompute(input[i+1:])
                for num1 in a:
                    for num2 in b:
                        if input[i]=='+':
                            rel.append(num1+num2)
                        elif input[i]=='-':
                            rel.append(num1-num2)
                        else:
                            rel.append(num1*num2)

        return rel

时间一下就少了。。。

时空复杂度

在最坏情况下，比如 1+2+3+4+5 ，递归的深度为 4 ，所以最坏情况下递归深度为 N/2 ，所以总的时间为 N*(N/2 + len(a)*len(b)) ，故时间复杂度不会超过 O(N^3) 。

递归深度最坏为 N/2 ，则递归时用到的空间为 N/2 ，因为最外层有一个循环，所以总的空间复杂度不会超过 O(N^2)

此题具体的时空复杂度不太会分析，还望大佬们能够告知！