All you do is keep a history of Password + Salt. When you change the password you hash the password against all historical salts, if one of those matches then y

All you do is keep a history of Password + Salt. When you change the password you hash the password against all historical salts, if one of those matches then you know the password has been re-used.