leetcode-go/medium/306.additive-number.go

func isAdditiveNumber(num string) bool {
	n := len(num)
	if n < 3 { // At least 3 chars
		return false
	}
	for i := 1; i < (n+1)/2; i++ {
		if num[0] == '0' && i != 1 { // Avoid 00 + ...
			return false
		}
		for j := 1; j <= (n-i)/2; j++ {
			if num[i] == '0' && j != 1 { // Avoid ... + 0x
				break
			}
			var one, two int
			fmt.Sscan(num[0:i], &one)
			fmt.Sscan(num[i:i+j], &two)
			if search(num, i+j, one, two) {
				return true
			}
		}
	}
	return false
}

func search(num string, idx, one, two int) bool {
	n := len(num)
	if idx == n {
		return true
	} else if num[idx] == '0' {
		if one+two != 0 {
			return false
		}
		return search(num, idx+1, 0, 0) // 00000000... is valid
	}
	var three int
	for three = 0; three < one+two && idx < n; idx++ {
		three = three*10 + int(num[idx]-'0')
	}
	if three == one+two {
		return search(num, idx, two, three)
	}
	return false
}

type pair struct {
	_1 int
	_2 int
}