K (ngn/k), 44 43 39 37 bytes

*<==!/+/'\{'[#x^-/!2#,&:]_+!x:'2}@!1+

Try it online!

                                  !1+   range 0..n
          {                     }@      complete rulers:
                          +!x:'2          n+1-d range (0...)..(1...)
           '[           ]_                keep where
                -/!2#,&:                  distances
             #x^                            superset of range 0..n
   =!/+/'\                              group by #marks
*<=                                     min

JavaScript (ES7), 139 bytes

Returns the rulers as a space-separated string of bit-masks.

f=(n,N)=>(g=q=>--q?g(q)+((h=j=>~j?q>>j&1**h(j-1)&&a.push(a.map(x=>h|=1<<j+~x)&&j)<N:a=[])(n)+h>>n?q.toString(2)+" ":""):"")(2<<n)||f(n,-~N)

Try it online!

Slower but not limited by the size of the call stack: 140 bytes

Commented

f = (                   // outer recursive function taking:
  n,                    //   n = input
  N                     //   N = exclusive upper bound for the number of
) =>                    //       marks in the ruler (initially undefined)
( g = q =>              // inner recursive function taking q
  --q ?                 // decrement q; if it's not zero:
    g(q) +              //   append the result of a recursive call
    (                   //
      ( h = j =>        //   h is a recursive function taking j
                        //   NB: h is reused as a bitmask to test the ruler
        ~j ?            //   if j is not equal to -1:
          q >> j &      //     test the j-th bit of q
          1 ** h(j - 1) //     do a recursive call to h with j-1
          && a.push(    //     if the j-th bit is set, push j in a[] and
            a.map(x =>  //     for each value x in a[] (before the push):
              h |= 1 << //       update h by setting the bit at index j-x-1
                j + ~x  //       for a valid ruler, h will end up with all
            ) && j      //       bits from 0 to n-1 set to 1
          ) < N         //     test whether a[] has less than N elements
        :               //   else (end of recursion):
          a = []        //     initialize a[] to an empty array
      )(n) +            //   invoke h with n -> returns 1 if a.length < N
      h >> n ?          //   add this to h; if the n-th bit is set:
        q.toString(2)   //     success -> append the ruler as the binary
        + " "          //     representation of q followed by a space
      :                 //   else:
        ""              //     append nothing
    )                   //
  :                     // else (q = 0):
    ""                  //   stop
)(2 << n)               // initial call to g with q = 2 << n
|| f(n, -~N)            // if no ruler was found, try again with N+1

Charcoal, 34 bytes

Ｎθ≔ＥΦＸ²⊕θ⌊＆ι×ιＸ²…·¹θ⍘ι²ηΦη⁼Σι⌊ＥηΣλ

Try it online! Link is to verbose version of code. Explanation: Uses @GB's bitwise And trick to find complete rulers.

Ｎθ

Input n.

≔ＥΦＸ²⊕θ⌊＆ι×ιＸ²…·¹θ⍘ι²η

Check all numbers up to 2ⁿ⁺¹ to see which ones correspond to complete rulers, then convert those to binary strings.

Φη⁼Σι⌊ＥηΣλ

Output those binary strings with the equal fewest number of 1s.

Ruby, 86 bytes

->n{(1..2<<n).select{|x|(1..n).all?{|y|x&x<<y>0}}.group_by{|x|x.digits(2).sum}.min[1]}

Try it online!

First check which numbers are complete rulers, by means of arithmetic shift and bitwise and, then group by number of marks (popcount) and take the minimum.

Jelly, 16 bytes

‘ŒPŒcIQLƲÐṀLÐṂṬṚ

A monadic Link that accepts the ruler length, \$N\$, and yields all perfect rulers of length \$N\$ as lists of binary marks ordered numerically.

Try it online! Or see the test-suite.

How?

If we can assert that a ruler has implicit marks of \$0\$ and \$N\$, which I believe is part of the definition of a sparse ruler, then we know that \$N\$ is always in the set of all distances a ruler can measure and hence \$k \ge N\$. At the same time, we cannot hope to measure any distance greater than \$N\$ (as that is the length of our ruler!), so \$k=N\$. Furthermore, no ruler of length less than \$N\$ can make as many measurements (they can't measure \$N\$).

Thus I believe we can just look for those rulers of length up to \$N\$ with maximal measuring capability (i.e. the set \$\{1,2,\cdots,N\}\$) and then filter these rulers down to those with the fewest marks. (Please correct me if I've made a false assertion!)

‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
‘                - increment {N} -> N+1
 ŒP              - powerset {[1..N+1]}
                   -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                      i.e. all rulers of length <=N where the 0-mark is represented
                           by a value of 1 or higher while no value may exceed N+1
                           (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=8)
                           Note that there is, therefore, exactly one representation
                           present of every sparse-ruler of length N
         ÐṀ      - keep those maximal under:
        Ʋ        -   last four links as a monad:
   Œc            -     unordered pairs
     I           -     forward deltas
      Q          -     deduplicate
       L         -     length
            ÐṂ   - keep those minimal under:
           L     -   length
              Ṭ  - untruth (convert to their binary representations)
               Ṛ - reverse (equivalent to sorting by binary representation)

Pyth, 26 bytes

.mSbf.Amsm}`11%hd>TkQQ^`Th

Try it online!

Alternatively +1 byte to seperate by newlines.

Explanation

.mSbf.Amsm}`11%hd>TkQQ^`ThQ    # implicitly add Q
                               # implicitly assign Q = eval(input())
                       `T      # string "10"
                      ^  hQ    # Q+1 times repeated cartesian product (this generates all binary strings of lenght Q+1)
    f                          # filter list on lambda T
       m             Q         #   map range(Q) over lambda d
         m          Q          #     map range(Q) over lambda k
          }`11                 #       check whether "11" is in
              %hd              #       the string made from taking every (d+1)-th character of
                 >Tk           #       T[k:]
        s                      #     sum (check if at least one boolean is true) the following
     .A                        #   check if all items in list are truthy
.m                             # filter for elements which minimize lambda b
  Sb                           #   sort the characters in b

05AB1E, 33 bytes

>EÝN.Æεœ.Δ.ÆíÆêILQ}}®KZdiIÝδå{që\

Try it online or verify \$n\$ in the range 1-7.

If binary-strings are mandatory, a J can be added after the { for +1 byte:
Try it online or verify \$n\$ in the range 1-7.

Explanation:

>                  # Increase the (implicit) input by 1
                   # (for edge-cases n=1 and n=2 that have larger output-rulers)
 E                 # Loop `N` in the range [1,input+1]:
  Ý                #  Push a list in the range [0,(implicit) input]
   N.Æ             #  Pop and push a list of all `N`-sized combinations
      ε            #  Map over each inner list:
       œ           #   Get all permutations of this list
        .Δ         #   Get the first that's truthy for:
                   #   (or -1 if none are truthy)
          .Æ       #    Pop the list and get all combination-pairs
            í      #    Reverse each inner pair
             Æ     #    And then reduce each pair by subtracting
                   #    (these are all sizes this ruler can measure)
              ê    #    Uniquify and sort it
               IL  #    Push a list in the range [1,input]
                 Q #    Check that the two lists are the same
         }         #   Close the find_first
      }            #  Close the map
       ®K          #  Remove all -1s
         Zdi       #  If valid rulers have been found:
            IÝ     #   Push a list in the range [0,input] again
              δ    #   Apply double-vectorized:
               å   #    Check for each value in [0,input] if it's in the ruler
                   #   (we now have a list of binary-lists)
                {  #   Sort this list of binary-lists
                 q #   Stop the program
                   #   (after which the list of binary-lists is output implicitly)
           ë       #  Else:
            \      #   Discard the empty list (so we can use the implicit input
                   #   for the next iteration again)