[onnodigcomplex]

You can first divide the solution in two parts, 1) the letter selection and 2) finding a valid permutation.

There's a fairly finite set of letters that you might want to enumerate based on both your initial 'seed' text and the letters that are in the numbers especially if you consider 'one [a-z]' as seed text. That is to say, the amount of sets of letters that have different sets of numbers that you can spell with them is small.

If you know what letters you have to write and you know all of those must have 2 or more instances you can add the "'s"'s and single instances of those letters to the seed text. At that point you just need to worry about selecting numbers that including their own letter counts sum to the seed text constant. This can be easily expressed in an ILP.

The ILP will define a 26 boolean array for each possible number we can spell representing whether that number is the count of that letter. We add a constraint that the sum of all active numbers on a given letter == 1. Next we simply add constraints that sum all active numbers their lettercounts to the known constants from the seed text.

But as it turns out that is overkill, a more traditional and flexible solution would involve a tree search that keeps track of the lower and upper bounds of lettercounts and picks number words within those bounds without associating it with a specific letter yet. And you associate at the end. Runtime is a 15 minutes in python for most numeric bases/seed texts/variations.