Adding contact on iPhone adds it to Exchange but not iCloud
Yes, it is possible.

Set the default account for Contacts to iCloud. That will add new contacts to iCloud.

To do this


Tap Settings -> Mail, Contacts, Calendars
Scroll to Contacts, about 2/3rds down the page.
Tap Default Account and then choose iCloud.