package main

import (
	"fmt"
	"math"
	"strconv"
)

func splitIntoFibonacci(S string) (res []int) {
	trace , n ,sumLen := make([]string,0,0) , len(S) ,0
	maxStr := strconv.Itoa(math.MaxInt32)
	var depth func(idx int)
	depth = func(idx int)  {
		tn := len(trace)
		//	用打印来调试回溯算法非常的方便。重点打印trace即可发现毛病 ,稍微臃肿不是毛病，逻辑完备就好.
		if len(res) > 0 || (tn > 2 && !(strSum(trace[tn-2] ,trace[tn-3]) == trace[tn-1])) {
			return
		}
		if n == sumLen  && (len(trace) > 2 && strSum(trace[tn-2] , trace[tn-3]) == trace[tn-1]) {
			for _ , v := range trace {
				Val , _ := strconv.Atoi(v)
				res = append(res, Val)
			}
			return
		}

		for i := idx + 1 ; i <= n ; i++ {
			if S[idx] == '0' && i - idx > 1{
				break
			}
			if strCompare(S[idx:i],maxStr) {
				break
			}
			sumLen += i -idx
			trace = append(trace, S[idx:i])
			depth(i)
			if len(res) > 0  {
				return
			}
			trace = trace[:len(trace)-1]
			sumLen -= i -idx
		}
	}
	depth(0)
	return res
}

func strSum(ls , ss string) (res string) {
	n1 , n2 := len(ls) , len(ss)
	if n1 < n2 {
		ls , ss = ss ,ls
		n1 , n2 = n2 , n1
	}
	idx, pos := 0 , 0
	for idx < n2 {
		v1 , v2 := ls[n1-1-idx] - '0' , ss[n2-1-idx] - '0'
		res = strconv.Itoa((int((v1+v2))+pos)%10) + res
		pos = (int(v1 + v2) + pos) / 10
		idx ++
	}
	// 添加pos和剩余位
	for idx < n1  {
		v := pos + int(ls[n1-1-idx] - '0' )
		res = strconv.Itoa(v%10) + res
		pos = v / 10
		idx ++
	}
	if pos != 0 {
		res = "1" + res
	}
	return res
}

func strCompare(s1,s2 string) bool {
	if len(s1) > len(s2) {
		return true
	}
	if len(s1) == len(s2) {
		return s1 > s2
	}
	return false
}




func main() {
	fmt.Println(splitIntoFibonacci("3611537383985343591834441270352104793375145479938855071433500231900737525076071514982402115895535257195564161509167334647108949738176284385285234123461518508746752631120827113919550237703163294909"))
	fmt.Println(int32(1 << int32(31) -1 ))
	fmt.Println(math.MaxInt32)
}