Self balancing btrees will keep your set split roughly in half. So basically, you just insert elements and let the tree worry about remaining balanced.
This isn't a question of data structures: What bmichel is saying is that enumerating a nonpolynomial number of items isn't something you can do as a step in a polynomial reduction.
