I want to keep a list of things I've already encountered in my recursive looping so I can avoid recalculating the same things over and over again. What is the most efficient data structure for this?
Looking at complexity analysis, Hashtables seem to be the most efficient for lookups. However, it feels inefficient to hold a data structure of key value pairs when all I'm interested in is looking up whether a specified key exists.
I thought that maybe a set would be a good idea, but its complexity doesn't seem to indicate so.
A set probably is the correct abstract data type for this, since really the only information it encodes is whether an item is inside or not.
Using a set doesn't specify a particular implementation though. In most contexts, you should be able to find a set type implemented using hashing, or some type of tree structure. Which one you choose would depend on if the data you're inserting can be efficiently hashed or ordered.
In some libraries you will find set types that are implemented using the library's map types, but where the value is ignored. For example in rust, the standard library's HashSet type is implemented using the HashMap type.