The most intuitive solution you will ever find in this entire discussion. Plus, the run time speed surpassed editorial solution.

include

using namespace std;

int ipow(const int& b, const int& e){ if(e == 0) return 1; return b * pow(b, e - 1); }

int recursion_ans(const vector& vec, const int& index, const int& remaining){ if(remaining == 0) return 1; if(index < 0 || remaining < 0) return 0;

return recursion_ans(vec, index - 1, remaining - vec[index]) + 
        recursion_ans(vec, index - 1, remaining);

}

int main(){ int X, N; cin >> X >> N;

vector<int> vec;

int i = 1;
while(i){
    int value = ipow(i, N); ++i;
    if(value > X) break;
    vec.push_back(value);
}

cout << recursion_ans(vec, vec.size() - 1, X);

return 0;

}

Haskell

Function wwo -- "with or without"

module Main where

vals :: Int -> Int -> [Int]
vals n k = reverse $ takeWhile (<= n) [x ^ k | x <- [1 ..]]

wwo :: Int -> [Int] -> Int
wwo n xs
  | n == 0 = 1
  | n < 0 = 0
  | null xs = 0
  | otherwise = wwo n (tail xs) + wwo (n - head xs) (tail xs)

main :: IO ()
main = do
  n <- readLn :: IO Int
  k <- readLn :: IO Int
  print $ wwo n (vals n k)

int findPows(int X, int num, int N) {

int val = X - pow(num, N);
if (val < 0) {
    return 0;  
}
if (val == 0) {
    return 1;  
}

return findPows(val, num + 1, N) + findPows(X, num + 1, N); 

}

int powerSum(int X, int N) { return findPows(X, 1, N); }

knapsack, O(X * X^(1/N))

int powerSum(int X, int N) {
    int L = pow(X, 1.0/N);
    vector<vector<int>> cache(X+1, vector<int>(L+1));
    for (int j=0; j <= L; j++) cache[0][j] = 1;
    for (int i=1; i <= X; i++) {
        for (int j=1; j <= L; j++) {
            if (i < pow(j, N)) cache[i][j] = cache[i][j-1];
            else cache[i][j] = cache[i][j-1] + cache[i - pow(j, N)][j-1];
        }
    }
    return cache[X][L];
}

I noticed X was capped to 1000 and I'd never need to try any number >sqrt(1000), which happens to be just under 32. So, what I did was precompute the Nth powers for [1..32], store my current set as a bitmap in a u32. and then add when the bit was on. I just iterated until the first power of 2 (which means it's a single element set) for which the sum (the actual Nth power, in this case) was > X, since that means it's the Nth root of X and thus no point trying anything else. I'm somewhat proud of how dumb my solution was. No recursion, no algorithms concepts (although that's what I'm here to train :'( ).

fn powers(N: i32) -> [i32; 32] {
    let mut P = [0i32; 32];
    P[0] = 1;

    for (i, j) in (1..32usize).zip(2..33i32) {
        P[i] = j.pow(N as u32);
    }

    P
}
 
fn powerSumS(S: u32, P: &[i32]) -> i32 {
    let mut acc = 0;
    for bit in 0..32 {
        acc += P[bit] * (S & (1 << bit) != 0) as i32;
    }
    acc
}

fn powerSum(X: i32, N: i32) -> i32 {
    let mut current_set = 2u32;
    let mut count = 0;
    let P = powers(N);
    loop {
        let sum = powerSumS(current_set, &P);
        count += (sum == X) as i32;
        // We never need to explore further from sqrt(X)
        if current_set.is_power_of_two() && sum > X {
            break;
        }
        current_set += 1;
    }
    count
}