With the growing number of publicly available Web APIs, developers often struggle to identify compatible and effective web API compositions to meet the requirements of complex application requirements. API composition recommendation has thus emerged as a key enabler for mashup development. However, most existing approaches rely solely on graph-based search algorithms over API correlation graphs, lacking a principled mechanism to assess the utility of candidate API compositions. To overcome this limitation, we propose OSWAR (Optimal Subset Web API Recommendation), a two-stage framework for API composition recommendation. In the recall phase, OSWAR identifies candidate compositions by performing a minimum Steiner tree search on an API correlation graph, ensuring functional completeness and compatibility. In the recommendation phase, we introduce an optimal subset oracle that learns a utility-based scoring function via variational inference to re-rank candidate compositions. Extensive experiments on the real-world ProgrammableWeb dataset demonstrate that OSWAR significantly outperforms several state-of-the-art baselines in terms of Precision, Recall, F1-score, Hit Rate, and mAP, particularly excelling when recommending Top-1 API composition.