#include <iostream>
#include <vector>
 
template<class Iterator>
void get_substrings_aux(std::vector<std::string>& subs, Iterator lo, Iterator hi) {
	if(lo == hi) return;
	const std::size_t n = subs.size();
	subs.reserve(2*n);
	auto c = *lo;
	for(std::size_t i = 0 ; i < n ; ++i) { subs.emplace_back(subs[i] + c); }
	get_substrings_aux(subs, ++lo, hi);
}
 
std::vector<std::string> get_substrings(const std::string& str) {
	std::vector<std::string> subs(1);
	get_substrings_aux(subs, str.begin(), str.end());
	subs.erase(subs.begin());
	return subs;
}
 
int main() {
	std::string str("1234");
	auto subs = get_substrings(str);
	for(const auto& s : subs) std::cout << s << std::endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKdGVtcGxhdGU8Y2xhc3MgSXRlcmF0b3I+CnZvaWQgZ2V0X3N1YnN0cmluZ3NfYXV4KHN0ZDo6dmVjdG9yPHN0ZDo6c3RyaW5nPiYgc3VicywgSXRlcmF0b3IgbG8sIEl0ZXJhdG9yIGhpKSB7CglpZihsbyA9PSBoaSkgcmV0dXJuOwoJY29uc3Qgc3RkOjpzaXplX3QgbiA9IHN1YnMuc2l6ZSgpOwoJc3Vicy5yZXNlcnZlKDIqbik7CglhdXRvIGMgPSAqbG87Cglmb3Ioc3RkOjpzaXplX3QgaSA9IDAgOyBpIDwgbiA7ICsraSkgeyBzdWJzLmVtcGxhY2VfYmFjayhzdWJzW2ldICsgYyk7IH0KCWdldF9zdWJzdHJpbmdzX2F1eChzdWJzLCArK2xvLCBoaSk7Cn0KCnN0ZDo6dmVjdG9yPHN0ZDo6c3RyaW5nPiBnZXRfc3Vic3RyaW5ncyhjb25zdCBzdGQ6OnN0cmluZyYgc3RyKSB7CglzdGQ6OnZlY3RvcjxzdGQ6OnN0cmluZz4gc3VicygxKTsKCWdldF9zdWJzdHJpbmdzX2F1eChzdWJzLCBzdHIuYmVnaW4oKSwgc3RyLmVuZCgpKTsKCXN1YnMuZXJhc2Uoc3Vicy5iZWdpbigpKTsKCXJldHVybiBzdWJzOwp9CgppbnQgbWFpbigpIHsKCXN0ZDo6c3RyaW5nIHN0cigiMTIzNCIpOwoJYXV0byBzdWJzID0gZ2V0X3N1YnN0cmluZ3Moc3RyKTsKCWZvcihjb25zdCBhdXRvJiBzIDogc3Vicykgc3RkOjpjb3V0IDw8IHMgPDwgc3RkOjplbmRsOwoJcmV0dXJuIDA7Cn0=