連絡先謝って削除してしまいました

auの連絡先は、もともとauのExchangeサーバというところで管理されていました。このサーバとiPhoneを繋ぐのがauの「◎Eメール」プロファイルです。

この「◎Eメール」プロファイルがインストールされていると、設定を変更しない限り連絡先は全てサーバに書き込まれ、そのサーバ上にあるデータをiPhoneが参照しているだけという状況になります。
もちろん、サーバはauのサービスなので、契約解除とともにサーバ上のデータは削除されます。

しかし契約解除後も「◎Eメール」プロファイルが残っていれば、連絡先データはiPhone上に残り、そのまま使うことができます。

しかし、このデータは残念ながらiTunes、iCloud、どちらにもバックアップで残すことができません。
https://support.apple.com/ja-jp/ht204136
「ほかのクラウドサービス (Gmail、Exchange メールなど) で保管されているデータ」に該当します。

iPhone5s〜iPhone６あたりが主流の時期に、連絡先が消えたと大騒ぎになり、その後に仕様変更されたプロファイルがauから出たと記憶しています。
なので、auのプロファイルを削除して連絡先が消える人と、消えない人がいます。それは、おそらくプロファイルの種類の問題かもしくは既に別の場所にデータ移行をされていた状態かと思われます。

結論としては、auをすでに解約している場合、サーバ上にもiPhone上にも、連絡先データは残っていません。戻すことは不可能です。

残る可能性としては、何らかの操作で別の場所に連絡先データが移行され、それが残っていないか探すこととなります。
その探す先で一番有力なのが、iCloudサーバ内です。https://www.icloud.com/

iPhoneのSafariではうまくアクセスできないので、タブレットやパソコンを利用されることをおすすめします。

また、Gmailを利用されていたり、他の連絡先を保存しiPhoneと同期できるサービスを利用されている場合には、そちらも探す対象にはなります。