Burst Balloons (INITIAL APPROACH)

#include <bits/stdc++.h>
using namespace std;
//might not work, as it generates subsequence, so in the base case after processing all the balloons, some balloons will not be burst, some will be burst.
//But our answer can only depends on what order ALL the ballons should be burst, not how many or which one.
// We burst all but what order to burst to maximise profit
//not subsequence ..subsequence(abc) = '', a, b, c, ab..... (all valid subsequence, we don't want this, some chosen some not)
// permutations ... permutations(abc) = abc, bac,cba.... (all valid permutations, the whole string is present, just the order is changed, analogy = ALL balloons MUST be BURST, not some, to maximise profit, whether stated in question or not)
//If I need to rob banks a,b and c ... to maximise the profit I will rob all the banks, why leave some????
int burstBalloons(int level, vector<int> &nums){
    if(level >= nums.size()){
        return 0;
    }
    int burst = 0, notBurst = 0;
    //levels = each balloon
    //options = burst it or not


    //if burst, take coins of left and right balloon and burst the level balloon
    int coinInBallon = nums[level];
    //burst the level balloon
    nums[level] = 0;

    int leftBalloon = 1, rightBalloon = 1;
    for(int i = 0, j = nums.size() - 1; i < nums.size(); i++, j--){
        //get the just left balloon
        if(i < level && nums[i] != 0){
            leftBalloon = nums[i];
        }
        //get the just right balloon
        if(j > level && nums[j] != 0){
            rightBalloon = nums[j];
        }
    }
    cout << leftBalloon << " " << coinInBallon << " " << rightBalloon << '\n';
    burst = (leftBalloon * coinInBallon * rightBalloon) + burstBalloons(level + 1, nums);
    //backtrack where balloon didn't burst
    nums[level] = coinInBallon;
    notBurst = burstBalloons(level + 1, nums);
    //cout << level << " " << burst << " " << notBurst << '\n';
    return max(burst, notBurst);
}


//try breaking all balloon at each level, try to get the order in which balloons are burst and maintain how many balloons are burst

int burstBalloons2(int burst, vector<int> &nums){
    //all balloons burst, we may have a potent answer(base case)
    //All the potent answer would have one thing in common, all the balloons should be burst (burst == nums.size())
    //We are trying every order in which they burst(every possibility), so our answer(maxCoins) would be among one of them
    //base case
    if(burst >= nums.size()){
        //no balloons left to burst, return 0 coins
        return 0;
    }
    //level = some anchor around which options explored(what could be a meaningful name for anchor)
    //options = breach each remaining balloon
    //it is not about some balloons left standing and some balloons burst (not subset/subsequence)
    //as we cannot maximise profit then (profit can be maximised only when all balloons burst)
    //We have to burst every balloon, just the order in which they should burst matters, try every order then(sort of generating permutations)
    int maxCoins = 0;
    for(int k = 0; k < nums.size(); k++){
        if(nums[k] != 0){
            int coinsInBalloon = nums[k];
            nums[k] = 0;
            int leftBalloon = 1, rightBalloon = 1;
            for(int i = 0, j = nums.size() - 1; i < nums.size(); i++, j--){
                //to get the just left balloon that is not burst
                if(i < k && nums[i] != 0){
                    leftBalloon = nums[i];
                }
                //to get the just right balloon that is not burst
                if(j > k && nums[j] != 0){
                    rightBalloon = nums[j];
                }
            }
            maxCoins = max(maxCoins, (leftBalloon * coinsInBalloon * rightBalloon) + burstBalloons2(burst + 1, nums));
            nums[k] = coinsInBalloon;
        }
    }
    return maxCoins;
}

int main() {
    // your code goes here
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    //memo key should be both (burst , nums)
    // as burst is getting used
    cout << burstBalloons2(0, nums) << '\n';
}