An even more space-efficient means of generating all the possible combination of MQTT wildcards and token arrangements for a given. Uses structural sharing of nodes wherever possible. Compare with first version

mqtt_generate_topics_V2.go

package main

import (
	"fmt"
	"strings"
)

type node struct {
	val         string
	exact       *node
	singleLevel *node
}

func populate(tokens []string) (e *node, s *node) {
	e, s = &node{val: tokens[0]}, &node{} // +
	if len(tokens) == 1 {
		return
	}
	e.exact, e.singleLevel = populate(tokens[1:])
	s.exact, s.singleLevel = e.exact, e.singleLevel
	return
}

func generateTopicStrings(tokens []string) []string {
	root := new(node)
	root.exact, root.singleLevel = populate(tokens)

	// the expected no. of pure single level topics is the number of leaves.
	// hence, if we have 3 levels e.g. from the topic foo/bar/quz, we'll
	// expect 2^3 pure single level tokens. Courtesy of binary representation
	// and bitshifts, this operation is equivalent to 1 << 3. Hence, with L levels
	// we get the result via 1 << l
	noTopics := (1 << len(tokens))

	// the expected no. of topics terminated by # ie a multilevel match is a geometric series.
	// Drawing out the tree, each and every node from the root can be extended
	// to have a '#' as a child. Suppose we have foo/bar/quz as the select topic.
	// At the zeroth level (ie root), we have 1 '#' since it matches every topic.
	// At the first level, we have 'foo/#' and '+/#' ie 2^1. At the second level, we have
	// 'foo/bar/#', 'foo/+/#', '+/bar/#' and '+/+/#' ie 2^2.
	// Hence with L levels, the expected result is 1 + 2^1 + 2^2 + ... 2^L.
	// Using the formula for summing geometric series and simplifying, we end up with 2^(L+1) - 1
	// Once again, courtesy of binary representation and bitshifts, this operation is equivalent to
	// 1 << (L+1) - 1, which is equal to 2 << L - 1
	noTopics += (2 << len(tokens)) - 1
	generatedTopics := make([]string, 0, noTopics)

	// ensure temp has enough space to avoid
	// unecessary allocations
	temp := make([]string, 0, len(tokens)+1)

	// ensure string builder has enough space to avoid unecessary allocations
	// the possible max length for a given generated string is the sum of the length of
	// each token plus space for the '/' separators plus a multilevel '#' at the end
	strBLen := 0
	for _, t := range tokens {
		strBLen += len(t)
	}
	strBLen += (len(tokens) + 1)

	// traverse the tree. On each leaf-node, a slice 'ts' temporarily holding
	// the tokens for a given generated topic shall be 'emitted'. Furthermore,
	// on both leaf-nodes and intermediary nodes, 'ts' shall be emitted with
	// the contents of multi-level match token
	traverse(root, temp, func(ts []string) {
		var strB strings.Builder
		strB.Grow(strBLen)

		strB.WriteString(ts[0])
		for _, t := range ts[1:] {
			strB.WriteByte('/')
			strB.WriteString(t)
		}
		generatedTopics = append(generatedTopics, strB.String())
	})

	return generatedTopics
}

func traverse(n *node, temp []string, emitTokens func([]string)) {
	if n.exact == nil && n.singleLevel == nil { // is leaf
		emitTokens(temp)
	} else { // is intemediary
		traverse(n.exact, append(temp, n.exact.val), emitTokens)
		traverse(n.singleLevel, append(temp, "+"), emitTokens)
	}
	emitTokens(append(temp, "#"))

}

func main() {
	// assume a given topic 'foo/bar/quz' is already split
	// into its constituent tokens
	tokens := []string{"foo", "bar", "quz"}
	ts := generateTopicStrings(tokens)
	for _, t := range ts {
		fmt.Println(t)
	}
}