84. Different Ways to Add Parentheses

1.分割征服による複数の組合せ

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        
        def compute(left, right, op):
            results = []
            
            for l in left:
                for r in right:
                    results.append(eval(str(l) + op + str(r)))
                
            return results
        
        if expression.isdigit():
            return [int(expression)]
            
        results = []
        
        for index, value in enumerate(expression):
            if value in "-+*":
                left = self.diffWaysToCompute(expression[:index])
                right = self.diffWaysToCompute(expression[index + 1:])
                
                results.extend(compute(left, right, value))
        return results

かっこをどこに追加するかによって、いろいろな組み合わせができます.すべての組合せを計算します.これは、次の分割によって征服できます.