I’m trying to solve this challenge on HackerRank.

In short, given `x`

and `n`

, I have to determine how many ways I can pick numbers from the `n`

th powers of the natural numbers such that their sum is `x`

.

So my first reasoning was to compute the list of the `n`

th powers that I need as a first step. This list is

```
list = takeWhile (<= x) (i^n | i <- (1..))`
```

Now `list`

is the bucket from which I have to pick numbers to add up to `n`

.

I first thought about list comprehensions, because that’s how I would pick a **given** number of numbers from the list; for instance this is how I would generate the `sumList`

of the sums of any different triplets from `list`

:

```
sumList = (x + y + z | x <- list, y <- dropWhile (<= x) list, z <- dropWhile (<= y) list)
```

Then I would just need to `length $ filter (== x) sumList`

.

However, after some thinking, I concluded that list comprehensions are not the way to go, since I don’t know in advance how many numbers I have to pick from `list`

when attempting to sum them up to `x`

.

So I thought that any possible sum corresponds to a combination of *pick or not-pick* while traversing the `list`

. This made me think of binary trees, and I eventually came up with this solution, which fails the *Test Case 3* for timeout:

```
main :: IO()
main = do
(x,n) <- sequence $ replicate 2 ((read :: String -> Int) <$> getLine)
print $ length $ filter (== x) $ getLeaves $ listToSumTree $ takeWhile (<= x) (i^n | i <- (1..))
data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Show)
listToTreeImpl :: (Num a, Eq a) => (a) -> Tree a -> Tree a
listToTreeImpl () tree = tree
listToTreeImpl (l:ls) (Leaf x) = Node x
(listToTreeImpl ls $ Leaf x)
(listToTreeImpl ls $ Leaf (x + l))
getLeaves :: Tree a -> (a)
getLeaves (Leaf a) = (a)
getLeaves (Node _ (Leaf _) (Node _ _ _)) = error "this should not happen"
getLeaves (Node _ (Node _ _ _) (Leaf _)) = error "this should not happen"
getLeaves (Node _ left right) = getLeaves left ++ getLeaves right
listToSumTree :: (Num a, Eq a) => (a) -> Tree a
listToSumTree ls = listToTreeImpl ls (Leaf 0)
```

I can only think of `getLeaves $ listToSumTree`

as the only critical part of the program, since `listToSumTree`

constructs a full tree, which is not needed (only the leaves are), and `getLeaves`

traverses all the tree, only to get to the bottom layer of it.