Check if Number is a Sum of Powers of Three

This approach treats the problem as a variation of the classic Subset Sum problem. We first generate all powers of three that are less than or equal to n. Then, we use a recursive function to explore all possible subsets of these powers to see if any subset sums up to n. Since each power can either be included in the sum or not, this leads to a backtracking algorithm that checks all possibilities.

• Create a list of all powers of three (1, 3, 9, ...) that are less than or equal to the input n.
• Implement a recursive helper function, say canPartition(target, powers, index).
• The base cases for the recursion are:
  • If target is 0, it means we have found a valid combination of powers, so return true.
  • If target becomes negative or we have exhausted all available powers (index < 0), it's impossible to form the sum, so return false.
• In the recursive step, for each power powers[index], we explore two choices:
  • Include: Subtract the current power from the target and recurse on the remaining powers: canPartition(target - powers.get(index), powers, index - 1).
  • Exclude: Keep the target as is and recurse on the remaining powers: canPartition(target, powers, index - 1).
• If either of these recursive calls returns true, it means a valid sum is possible, and we propagate true up the call stack.

The core idea is to determine if n can be formed by a sum of a subset of the available powers of three. We can model this with a recursive function that makes a decision for each power of three: either use it in the sum or don't. This exploration of all possibilities guarantees finding a solution if one exists.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean checkPowersOfThree(int n) {
        List<Integer> powers = new ArrayList<>();
        int p = 1;
        while (p <= n) {
            powers.add(p);
            // Prevent integer overflow before multiplication
            if (p > Integer.MAX_VALUE / 3) {
                break;
            }
            p *= 3;
        }
        // Start recursion from the last element of the list (largest power)
        return canPartition(n, powers, powers.size() - 1);
    }

    private boolean canPartition(int target, List<Integer> powers, int index) {
        // Base case: successful partition
        if (target == 0) {
            return true;
        }
        // Base case: invalid path
        if (target < 0 || index < 0) {
            return false;
        }

        // Recursive step:
        // 1. Try to form the sum including the current power
        if (canPartition(target - powers.get(index), powers, index - 1)) {
            return true;
        }

        // 2. Try to form the sum excluding the current power
        return canPartition(target, powers, index - 1);
    }
}