Smart health exploits smart health devices (e.g., fitness trackers, heart rate or glucose monitoring units) and Internet of Things technologies to improve users' health and wellness. By enabling self-monitoring and data sharing among users and healthcare professions, smart health can increase healthy habits, timely treatments, reduce hospital visits/re-admissions and even save lives. While smart health comes with great benefits, it also poses a privacy threat to the re-identification of users and their personal data. This paper presents an approach to protecting users' privacy by generalizing critical data so that they belong to multiple users as a way to anonymize user identity. Unlike existing anonymization techniques, our approach efficiently produces shared data that satisfy user-specified anonymity requirements while keeping the data as informative as possible. The approach is based on an Artificial Intelligence search technique using two proposed heuristics. The paper describes and illustrates the approach with experiments to compare its effectiveness with other techniques. The results show that, given a trade-off of privacy preserving, data retention and computational cost, our approach gives the most effective solution for data sharing as expected.