This code reaches time limit on 1 test case, solving this challenge. The approach that I'm using is from the book Algorithms Functional Programming Approach, which is a backtracking depth searching method. How do I improve speed of this code? Or is there better way to do it?
searchDfs :: (Eq node) => (node -> [node]) -> -- generates successor nodes (node -> Bool) -> -- is goal node -> -- first node [node] searchDfs succ goal x = search' ([x]) where search' s | null s =  | goal (head s) = head s : search' (tail s) | otherwise = let x = head s in search' (succ x ++ tail s) type Degree = Int type CurrentSum = Int type CurrentNumber = Int type Node = (CurrentSum,CurrentNumber,Degree,Goal) type Goal = Int succN :: Node -> [Node] succN (sum,i,d, goal) = [( sum+i'^d, i', d, goal) | i' <- [(i+1)..goal], sum+i'^d <= goal ] goal :: Node -> Bool goal (sum,_,_,m) = sum == m countSols :: Degree -> Goal -> Int countSols d m = foldr (+) 0 $ map (\(sum,i) -> length (searchDfs succN goal (sum,i,d,m))) startingNumbers where startingNumbers = [ (i^d,i) | i <- [1..m], i^d <= m] main = do m <- readLn d <- readLn let c = countSols d m print c