In Haskell. Two points: 1. pruning 2. Int suffers from overflow. Integer it is.

getPowerSum :: Integer -> [Integer] -> Integer -> IntegergetPowerSum _ [] _           = 0getPowerSum tgt cand start = case compare tgt start of                                                             EQ     -> 1                                LT    -> 0                                GT  ->     let newCand = filter (>start) cand in                                        let newTgt  = tgt - start in                                        sum $ map (getPowerSum newTgt newCand) newCandgetPowerSumWays :: Integer -> Integer -> [Integer]getPowerSumWays x n = let cand = [i^n | i <- [1..x], (i ^ n) <= x] in                      map (getPowerSum x cand) cand                                            -- Main --main = do    sx <- getLine    sn <- getLine    let x = read sx :: Integer    let n = read sn :: Integer    print $ sum $ getPowerSumWays x n