package mainimport (	"fmt")/*Perfect Squares My Submissions QuestionGiven a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.For example,  given n = 14, return 3 because 14 = 1 + 4 + 9.*/var arr = []int{1, 4, 9, 16}func addsequence(arr []int, num int) {	result := searchback(arr, num, 0)	if result == 1 {		fmt.Printf("the seq number can add to %v\n", num)	} else {		fmt.Printf("the seq number can not add to %v\n", num)	}}func searchback(arr []int, num int, index int) int {	length := len(arr)	if index == length {		return -1	}	tmp := num - arr[index]	if tmp == 0 {		return 1	} else if tmp > 0 { //只有大于0的时候往下探索		res := searchback(arr, tmp, index+1)		if res == 1 {			return 1		} else {			return searchback(arr, num, index+1)		}	} else {		return -1	}}func main() {	addsequence(arr, 6)	addsequence(arr, 13)	addsequence(arr, 15)	addsequence(arr, 29)}

输出结果：

the seq number can not add to 6the seq number can add to 13the seq number can not add to 15the seq number can add to 29