Sounds like something Relevanssi could handle. With Relevanssi, you’d have the checkboxes to choose the categories. Then, you’d write a function to hook on ‘relevanssi_modify_wp_query’ filter, where you’d read the checkboxes and convert them to a comma-separated list of category ID’s. That you would store in $wp_query->query_vars[‘cats’] and hey presto, Relevanssi gives you relevant results in those categories.
I think the same idea might work with default search, actually, but instead of ‘cats’ you’d use ‘cat’ and instead of ‘relevanssi_modify_wp_query’ you’d need another way to modify the $wp_query.