Baloon Burst - TLE

class Solution {
  unordered_map<string, int> memo;
public:

  typedef struct {
    int left;
    int itsVal;
    int right;
  } Baloon;

  int h_maxCoins(vector<Baloon> &nums) {

    string key = "";
    for(auto &x: nums){
      key+= to_string(x.left) + "|" + to_string(x.itsVal) + "|" + to_string(x.right) + "||";
    }

    if(memo.count(key)) return memo[key];


    int answer = 0;
    for(int i=0; i<nums.size(); i++){

      if(nums[i].itsVal == -1) continue;

      //else we can burst it..
      int tempAns = nums[i].itsVal;
      if(nums[i].left >= 0) tempAns *= nums[nums[i].left].itsVal;
      if(nums[i].right < nums.size()) tempAns *= nums[nums[i].right].itsVal;



      int temp1 = nums[i].itsVal;
      int temp2, temp3;
      nums[i].right <  nums.size() ? (temp2 = nums[nums[i].right].left) : 0;
      nums[i].left >= 0 ? (temp3 = nums[nums[i].left].right) : 0;

      nums[i].itsVal = -1;
      nums[i].right < nums.size() ? (nums[nums[i].right].left = nums[i].left) : 0;
      nums[i].left >= 0 ? (nums[nums[i].left].right = nums[i].right) : 0;
      tempAns += h_maxCoins(nums);

      nums[i].itsVal = temp1;
      nums[i].right < nums.size() ? ( nums[nums[i].right].left = temp2 ): 0;
      nums[i].left >= 0 ? (nums[nums[i].left].right = temp3) : 0;

      answer = max(answer, tempAns);
    }
    memo[key] = answer;
    return answer;
  }

  int maxCoins(vector<int>& copy) {
    vector<Baloon> nums(copy.size());

    for(int i=0; i<copy.size(); i++){
      nums[i].left = i-1;;
      nums[i].right = i+1;
      nums[i].itsVal = copy[i];
    }

    return h_maxCoins(nums);
  }
};