The matchesSum check is constant in the length of the input list. The filter adds an iteration over all results of (combinations n xs). If the complexity of (co

The matchesSum check is constant in the length of the input list. The filter adds an iteration over all results of (combinations n xs). If the complexity of (combinations n) is T(n) in xs, then by analogy of its recursive definition we have two recursive calls that are T(n-1), we have an fmap that is O(1) and a concatenation that is O(1). That sets up the recurrence T(n) = 2T(n-1) making the (combinations n) function O(n) in xs. Thus the whole thing is O(n²). It's not like this is particularly hard for Haskell. If anything, it's often easier because we can set up the recurrence by analogy with the definition.