指尖劃過的軌跡，藏着最細膩的答案~

題目：

給你一個整數 n ，如果你可以將 n 表示成若干個不同的三的冪之和，請你返回 true ，否則請返回 false 。

對於一個整數 y ，如果存在整數 x 滿足 $y == 3^x$ ，我們稱這個整數 y 是三的冪。

示例 1：

輸入：n = 12
輸出：true
解釋：$12 = 3^1 + 3^2$

示例 2：

輸入：n = 91
輸出：true
解釋：$91 = 3^0 + 3^2 + 3^4$

示例 3：

輸入：n = 21
輸出：false

提示：

$1 <= n <= 10^7$

分析：

示例 1 的 n=12=9+3。其中 9 是最大的小於等於 12 的 3 的冪。

如果不從 12 中分出 9，那麼 12 必須表示為更小的 3 的冪之和，即 12=(3+3+3)+3，相當於把 9 分成了若干個相同的 3。題目要求不能有相同元素，3 必須繼續分解，但這會得到更多的 3 的冪，即 3=1+1+1。所以，如果不從 12 中分出 9，就無法滿足題目要求。

一般地，必須分解出小於等於 n 的最大 3 的冪 $3^k$，然後問題變成 $n′=n−3^k$，這是一個規模更小的子問題。該方法也是把 n 表示為三進制的方法之一。例如 $12=110_{(3)}$，$21=210_{(3)}$。

示例 3 的 n=21=9+9+3，一旦出現兩個相同的 3 的冪，即使把其中一個 9 繼續分成更小的 3 的冪，仍然會有相同的 3 的冪。這意味着如果 n 的三進製表示中有數字 2，那麼 n 就無法表示成若干個不同的三的冪之和。否則，n 可以表示成若干個不同的三的冪之和。

作者：靈茶山艾府

參考代碼：

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
};