Why does my apps script deployed as API executable return Permission Denied?

I created a script in the script editor, published it as a "Deploy as API executable". Inside this script, I provided a doc_id to my sheet and defined a function to get data from that sheet.

I then went to https://developers.google.com/apps-script/execution/rest/v1/scripts/run to test the execution API. I added the scopes, authorized the app and tried it. I am getting the following error message:

"error": {
  "code": 403,
  "message": "The caller does not have permission",
  "status": "PERMISSION_DENIED"
}

Can someone tell me what I am doing wrong?

Make sure the app script is associated with correct dev console project.

The script should be associated with the dev console project id that corresponds with OAuth 2.0 client ID used (this dev console project should also have "Apps Script Execution API" enabled).

To change the developer console project for an app script select the following menu item: Resources > Developer Console Project...

On this screen enter the project number for your dev console.

Even with everything okay, you can get that error by "devMode":true. Thanks to this, I wasted half a day when I tried to deploy for other users.

Just for the future reference.

You just have to add the service account user as an editor on the project

The email from the service account to add looks something like this {project-name}@{project-name}.iam.gserviceaccount.com

I did a mix of all of your suggestions, plus I needed to use the non 'obsolete' ID of the Project. When I publish the script, it gives me an ID, which I was using succesfully as long as owner runs the routine, and only within Google Chrome (If I try it on Edge it fails). When I publish and try it with a different user it stop working. I open the script, go to file / Project properties and copy the longer Script ID instead. The routine start working for any user then. In the following image I underscore in red the key that Works for developer alone, and in Green the key that Works for all users (they're cutted in purpouse, and my environment is in spanish so actual translated options may vary, sorry)

I believe it is worth to make a summary:

1. I follow intructions at 'Using the execution API' and quickstarts to publish my script as execution API. (Create the script, enable Google Apps Script Execution API, publish as API executable with Access by everybody)
2. I made the script visible fro everybody, on File / Sharing:
3. I made sure that devMode was not set true on my call. Here the JavaScript call snipet:
4. I made sure that all of the scopes in the Project were included during the OAuth request:
5. I have to wait a few minutes to get all security rights to get ready (i.e. OAuth credentials)

Basically, these are all the required steps I needed to follow in order to get the script up and running. Hope it helps. Finally I would like you to see what I saw when it failed and when it succeeded:

Thank you!

I've also faced with the error and everything were associated accordantly... After some time of investigation I found out that sheet should be shared by link. This is a limitation of googleapis v4.