What about solving the problem with DP?

Use DP with two states dp[pos][cnt], where pos represents the pos-th coin and cnt is the number of heads seen so far.

You can do the transitions with a little bit math.

For the base case, when pos == n return (cnt == target) to filter out the invalid scenarios.