func PowOfThree(n int) { res := make([]int, 0) var backTrack func(int) backTrack = func(curr int) { if curr == n { return } k, remain := 1, n-curr if remain > 0 { for k < remain { k *= 3 } } else { for k < (-remain) { k *= 3 } } if remain > 0 { if k-remain > remain { k /= 3 } res = append(res, k) backTrack(curr + k) } else { if k+remain > -remain { k /= 3 } res = append(res, -k) backTrack(curr - k) } } backTrack(0) print(n, "=") for i, v := range res { if i > 0 && v > 0 { print("+") } print(v) } println() }