leetcode-go/hard/282.expression-add-operators.go

func addOperators(num string, target int) (res []string) {
	strlen := len(num)
	exp := make([]byte, 2*strlen)
	DFS(num, strlen, target, 0, &exp, 0, 0, 0, &res) // O(n^4) time, O(n) space
	return
}

func DFS(num string, strlen, target, pos int, exp *[]byte, length, prev, curr int, res *[]string) {
	if pos == strlen && curr == target {
		*res = append(*res, string((*exp)[0:length]))
		return
	}
	n, i, l := 0, pos, length
	if pos != 0 {
		length++
	}
	for i < strlen {
		if num[pos] == '0' && pos < i { // Avoid leading zero
			break
		}
		n = n*10 + int(num[i]-'0')
		(*exp)[length] = num[i]
		length, i = length+1, i+1
		if pos == 0 { // Init DFS
			DFS(num, strlen, target, i, exp, length, n, n, res)
			continue
		}
		(*exp)[l] = '+'
		DFS(num, strlen, target, i, exp, length, n, curr+n, res)
		(*exp)[l] = '-'
		DFS(num, strlen, target, i, exp, length, -n, curr-n, res)
		(*exp)[l] = '*'
		DFS(num, strlen, target, i, exp, length, prev*n, curr-prev+prev*n, res)
	}
}