CareerCup

A and B are playing a perfect 8-9 game. The rules are pretty simple. At each point, you can either insert an 8 at the end of the previous number or a 9. one 8 and one 9 forms a pair. a 9 can only be inserted if there is an 8 which does not form a pair. Perfect solution is the one which has all its numbers in pair. Find out all the possible perfect outcomes of the game in lexicographic order.

Input-
Input 1: Max length of number

Output-
Your array must return an array of string s containing all possible outcomes.

Example 1:
Input: 4
Output: {"8899", "8989"}

Explanation: There can be only 2 possible outcomes out of 4 as nine must follow eight.

Example 2:
Input: 6
Output:{"888999","889899","889989","898899","898989"}

Explanation: The possible outcomes are 5.