public static int powerSum(int X, int N) {
    // Write your code here
        return powerSum(X, N, 0);
    }
    
    static int powerSum(int X, int N, int min){
       /*
            My solution: try, check and try again (backtracking)
            Base cases: 
                X < 0 -> try but fail (+0) -> try again
                X == 0 -> try and find (+1) -> continues try
            ** Numbers tried must be increment, starting at least with 1. 
            -> Reduces duplicate cases.
            Induction steps:
                Find satisfied numbers, try one of them (k)
                Minus X to k^N(1 case - 1 subproblem)
            Time complex: O((floor(log_N(X)))!)
        */
        
        if(X < 0){
            return 0; 
        } 
        if(X == 0){
            return 1; //true because of (X >= 1) condition
        } 
    
        int count = 0;
        int i = min + 1;
        while(exp(i,N) <= X){ //O(log_N(X))
            count += powerSum(X - exp(i,N), N, i);
            i++;
        }
        
        return count;
    }
    
    private static int exp(int n, int N){
        int ex = n;
        for(int i = 1; i < N; i++){
            n *= ex;
        }
        return n;
    }