目标
给你一个整数 n ，如果你可以将 n 表示成若干个 不同的 三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12
输出：true
解释：12 = 31 + 32示例 2：
输入：n = 91
输出：true
解释：91 = 30 + 32 + 34示例 3：
输入：n = 21
输出：false提示：
- 1 <= n <= 10^7
思路
判断一个整数 n 能否用若干个 不同的 3 的幂之和表示。
直接的想法是使用 dfs 从小到大判断 3 的幂选或者不选。
从数学的角度考虑，如果 n 的三进制表示中包含 2 那么就无法用不同的三的幂之和表示。
代码
/**
* @date 2025-08-14 9:54
*/
public class CheckPowersOfThree1780 {
class Solution {
public boolean checkPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2) {
return false;
}
n /= 3;
}
return true;
}
}
public boolean checkPowersOfThree(int n) {
return dfs(1, 0, n);
}
public boolean dfs(int d, int num, int n) {
if (num == n) {
return true;
} else if (num > n || d > n) {
return false;
}
return dfs(d * 3, num, n) || dfs(d * 3, num + d, n);
}
}
性能
