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.
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.