How to determine the count and set of words that can be made from a bag of letters and bag of words python

Question

I have a task where I want to return the count and list of words (from the bag of words) that can be made from the bag of letters as a tuple. Imagine that the letters and words are physical pieces and you need to match the letters to the words to complete the words. You're not allowed to use the same physical letter twice, and you're not allowed to use the same physical word twice unless they exist repeatedly in their respective bags. I get how to go about getting the list of possible words, but I'm not sure how to optimize it to select the possible words other than a brute force effort of generating all possible combinations of words.

Here's an example. Imagine you have a bag of letters (similar to Scrabble):

[ g t o g l v o r d e a b ]

and a bag of possible words:

[word bag got we love]

In this case, the answer should be (3, ['bag', 'got', 'love'])

I've found some similar "Find list of possible words" or recursive sum questions that could probably be adapted, but none where they find the possible concurrent set of words from a set of letters in Python.

Here is an example I found for C#:

Finding the set of words that can be spelled with a given set of letters

Here is an example for finding any list of words:

Python: find possible words that can be made from 7 random letters

Answer 1

The best "not-so-brute-force" approach I can think of, as long as you have a fairly limited set of words, is:

letters=Counter('gtoglvordeaby')
words=['word', 'bag', 'got', 'we', 'love', 'doggy', 'dolly']
found = []
for word in words:
    wordbag=Counter(word)
    for wk,wv in wordbag.items():
        if wv > letters[wk]:
            break
    else:
        found.append(word)
print(len(found), found)

(I just added one letter and a couple of words to check that it behaves correctly when a word requires more than one occurrence of a certain letter).

I would be interested in knowing about better algorithms, of course