leetcode-go/leetcode/medium/241.different-ways-to-add-parentheses.go

import (
	"strconv"
)

var m map[string][]int = make(map[string][]int)

func diffWaysToCompute(input string) (ans []int) {
	if _, ok := m[input]; ok {
		return m[input]
	}
	for i := range input { // Divide and conquer, use every operator to split input into 2 smaller sub-problems.
		if ch := input[i]; ch == '+' || ch == '-' || ch == '*' {
			for _, l := range diffWaysToCompute(input[:i]) {
				for _, r := range diffWaysToCompute(input[i+1:]) {
					if ch == '+' {
						ans = append(ans, l+r)
					} else if ch == '-' {
						ans = append(ans, l-r)
					} else {
						ans = append(ans, l*r)
					}
				}
			}
		}
	}
	if len(ans) == 0 { // No operator, just a number
		n, _ := strconv.Atoi(input)
		ans = append(ans, n)
	}
	m[input] = ans
	return
}