It's possible to enumerate the infinite number of addition chains with a fixed number of small steps by enumerating a finite (yet often large) space of different objects (graphs for example).
The standard approach taken is to recognize that fixing the small step count at say \(s\) limits the non-doubling steps \(f\) in a chain such that \(s \le f \le 3.271s\). This is Knuth's  Corollary to Theorem A in §4.6.3.
We can therefor enumerate some alternate object that had the doubling steps removed. Mathematically enumeration results in a union of convex sets. The format we use to describe these convex sets comes from .
For example, the enumeration for \(s=0\) is:
1 1 1 @(a)
// 1 is a unique value that matches this convex set
@(a) is \(2^a\)
1 1 1 is and unique convex set number, the number of bits and the number of free variables in the convex set.
1 2 2 @(a)+@(b)
We must have \(a > b \ge 0\) so we describe the bits from most significant to least.
Things may become clearer when we view \(s=2\):
1 3 3 @(a)+@(b)+@(c)
2 4 1 @(a)+@(a-5)+@(a-6)+@(a-7)
3 4 2 @(a)+@(a-3)+@(b)+@(b-1)
4 4 4 @(a)+@(b)+@(c)+@(d), a-b-c+d >= 0, -a+b+c-d >= -1
The comma separated list of conditions (\(a-b-c+d \ge 0, -a+b+c-d \ge -1\)) must be satisfied to match the convex set. Note that Knuth's  Theorem C in §4.6.3 gives 4 cases for 2 small steps generating 4 bit numbers. Two of those cases are combined above (Case 1 and 2 are convex set 4).
Flammenkamp  did the first computer enumeration of the \(s=3\) as an answer to question 15 in §4.6.3 in . While writing a program for the \(s=4\) case I was postprocessing convex sets to detect and remove overlaps because the output is so huge. I was able to prune the \(s=3\) case from the original 200 cases to 150.
3 Small Steps
I outline some of the work to do the 4 small step enumeration here:
4 Small Steps
 Knuth DE (1969), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA. , pp. 98-422.
 Flammenkamp A (1991), "Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers". Thesis at: Diplomarbeit an der Fakultät für Mathematik, Universität Bielefeld.