TRUST enables users to specify desired prediction confidence when generating counterfactual explanations. By directly optimizing for confidence targets using a Probabilistic Tsetlin Machine and Bayesian optimization, TRUST produces more robust and interpretable recourse than traditional boundary-based methods, achieving perfect robustness with low cost and high confidence on real-world datasets.