Check if Number is a Sum of Powers of Three

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that y == 3x.

 

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 31 + 32
Example 2:

Input: n = 91
Output: true
Explanation: 91 = 30 + 32 + 34
Example 3:

Input: n = 21
Output: false
 

Constraints:


Solution:

class Solution {
    public boolean checkPowersOfThree(int n) {
        List<Integer> powerof3 = new ArrayList();
        for (int i = 0; i < 20; i ++) {
            if (Math.pow(3, i) <= 10000000) {
                powerof3.add((int) Math.pow(3, i));
            } else {
                break;
            }
        }
        Collections.reverse(powerof3);
        return dfs(powerof3, n, 0);
    }
    
    private boolean dfs(List<Integer> powerof3, int n, int i) {
        if (n == 0) return true;
        if (i == powerof3.size()) return false;
        int power = powerof3.get(i);
        if (power > n) {
            return dfs(powerof3, n, i + 1);
        } else {
            return dfs(powerof3, n - power, i + 1) || dfs(powerof3, n, i + 1);
        }
    }
}