Find X contiguous segments in a range of integers
Here's a quick piece of pseudo-code off the top of my head.

Given maximum value m and number of non-empty segments n, do so:


  Call Helper(Empty List [passed by reference], Empty List [copied before passing or passed by copy], 0, m, n)


The helper function takes as input:


a reference to the output list of lists,
a list of segments to append more segments to
the lower bound or starting value
the upper bound or stopping value
the number of segments

function Helper(L, S, l, u, n):
  If n = 1 then append to L the list S.append(l, u)
  Else:
    For each t from l+1 up to u-n *inclusive*:
      Make a copy of S into S'
      Append to S' the pair (s, t)
      Call Helper(L, S', t+1, u, n-1)



As you can see, the only "trick" was perhaps just figuring that out you should use a helper function with more arguments to aid the recursion. Of course, different solutions may be possible.

A note here. It should be possible to change the implementation above slightly (e.g., using return values as opposed to passing L by reference) that one can memoize the result of each call for a given triple (l, u, n). Such a DP approach seems to me like it may make the program be significantly faster on large input. I assume this sort of problem has much sharing to be exploited using a DP approach.