Ways to Express an Integer as Sum of Powers | Leetcode 2787

class Solution {
    #define MOD 1000000007
    vector<int> powers;
    int mem[300+2][300+2];

    int binaryExponentiation(int a,int b){
        int res = 1;
        while(b){
            if(b&1)
                res *= a;
            a *= a;
            b /= 2;
        }
        return res;
    }
    int findWays(int pos,int target){
        if(target==0)                           return 1;//Valid combination
        if(pos==powers.size() or target<0)      return 0;//Invalid
        if(mem[pos][target]!=-1)                return mem[pos][target];

        int exclude = findWays(pos+1,target);
        int include = findWays(pos+1,target-powers[pos]);
        return mem[pos][target] = (exclude + include) % MOD;
    }
public:
    int numberOfWays(int n, int x) {
        for(int i=1;i<=n;++i){
            int power = binaryExponentiation(i,x);
            if(power>n)//Can't include any more powers
                break;
            
            powers.push_back(power);
        }
        for(int ele: powers)    cout<<ele<<", ";
        memset(mem,-1,sizeof(mem));
        return findWays(0,n);
    }
};
/*
public class Solution {
    private static final int MOD = 1_000_000_007;
    private List<Integer> powers = new ArrayList<>();
    private int[][] memo;

    // Fast exponentiation: a^b
    private int binaryExponentiation(int a, int b) {
        long res = 1;
        long base = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            b >>= 1;
        }
        return (int) res;
    }

    // Recursive count with memoization
    private int findWays(int pos, int target) {
        if (target == 0) return 1;
        if (pos == powers.size() || target < 0) return 0;
        if (memo[pos][target] != -1) return memo[pos][target];

        long excl = findWays(pos + 1, target);
        long incl = findWays(pos + 1, target - powers.get(pos));
        return memo[pos][target] = (int) ((excl + incl) % MOD);
    }

    public int numberOfWays(int n, int x) {
        // Generate all i^x ≤ n
        for (int i = 1; i <= n; i++) {
            int p = binaryExponentiation(i, x);
            if (p > n) break;
            powers.add(p);
        }

        // Initialize memo table
        memo = new int[powers.size() + 1][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return findWays(0, n);
    }
}

#Python
from functools import lru_cache

class Solution:
    MOD = 10**9 + 7

    def numberOfWays(self, n: int, x: int) -> int:
        # Generate all i^x ≤ n
        powers = []
        i = 1
        while True:
            p = pow(i, x)
            if p > n:
                break
            powers.append(p)
            i += 1

        @lru_cache(maxsize=None)
        def find_ways(pos: int, target: int) -> int:
            if target == 0:
                return 1
            if pos == len(powers) or target < 0:
                return 0
            # exclude current
            res = find_ways(pos + 1, target)
            # include current
            res += find_ways(pos + 1, target - powers[pos])
            return res % Solution.MOD

        return find_ways(0, n)
*/