"Bulls and cows" algorithm
Use char[n] instead of string to store each individual solution.
Copy just the eligible solutions to a brand new vector (as Ben Voigt said) instead of deletion.


Assume n&lt;=10. So, memory you need is less than 73Mb (i.e. twice 10*10!). Sequential memory access (#2) and avoiding pointer dereference (#1) means high performance on modern DDR memory.

UPDATE: Some notes on random or even non-random, but non-sequentional DDR memory read. Say, four 8-byte reads at addresses 0x8000 0x8100 0x8200 0x8300 will be slower than four 8-byte reads at 0x9000 0x9008 0x9010 0x9018, because in the later case all the data for the last reads (i.e. 0x9008 0x9010 0x9018) are already in processor 32-byte cache line (also, there are 64-byte cache lines in some processors). Each memory read (say, 8-byte read) transfers the whole 32-byte cache line from memory to processor cache.

Next, even the best possible optimizer can not decrease non-sequentional memory access latency (that is, the time between the memory address was calculated and the memory address contents was arrived into the processor)