I found myself with this problem:
The recommended solution was to uninstall and then reinstall Homebrew, so that's what I did... but I didn't do a "brew list" before to check which packages I had installed. Oops.
I do have a Time Machine backup of my Mac, so I thought I'd plug in the drive and then, using the Terminal, navigate to the backup volume and then to whatever directory/file Homebrew uses to keep its database of installed packages.
Which directory should it be?