Find all non-decreasing sequences given lenght and size I'm trying to find a solution for this exercise:


  Give the pseudocode of an algorithm which takes two positive integers
  n and k and prints all the non-decreasing sequences of length k
  (1,2,...,n).
  
  For example n=4, k=3:
  
  111 112 113 114 122 123 124 133 134 144 222 223 224 233 234 244 333
  334 344 444
  
  the complexity must be O(n S(n,k)) with S(n,k) the number of the
  sequences to print for n and k.


i think from the complexity required that a backtracking algorithm it's needed  but i could'nt solve it.

i tried something like this:

P(n,k,h: prefix length, S: sequence)

      if h == k then
           OUTPUT S
      else
         for i=1 to n do
             if(i&gt;=S[h]) 
                   S[h+1]=i;
                   P(n,k,h+1,S);
Hint. Given the available time complexity, a simple recursive algorithm should work. If you need a sequence of length $k$ from the set $\{m, \dots, n\}$ you either include $m$ or you don't.