Recursion

Subsets

class Solution {
public:
    void recursion(vector<int>& nums,vector<int> &ds,int ind,int n,vector<vector<int>> &ans){
           if(ind==n){
             ans.push_back(ds);
             return;
           }

           ds.push_back(nums[ind]);
           recursion(nums,ds,ind+1,n,ans);
           ds.pop_back();
           recursion(nums,ds,ind+1,n,ans);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> ans;
        vector<int> ds;
        recursion(nums,ds,0,n,ans);
        return ans;
    }
};

Subsetes II

Optimized

class Solution {
public:
    void recursion(vector<int>& nums,vector<int> &ds,int ind,int n,vector<vector<int>> &ans){
           ans.push_back(ds);

           for(int i=ind;i<n;i++){
            if(i!=ind && nums[i]==nums[i-1]) continue;
            ds.push_back(nums[i]);
            recursion(nums,ds,i+1,n,ans);
           ds.pop_back();
           }

    }
    vector<vector<int>> subsets(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> ans;
        vector<int> ds;
        recursion(nums,ds,0,n,ans);
        return ans;
    }
};

Using Set

class Solution {
set<vector<int>>st;
public:
void sets(vector<int>& nums,int index,int n,vector<int>&ds){
 if(index==n){
     st.insert(ds);
     return;
 }
 ds.push_back(nums[index]);
 sets(nums,index+1,n,ds);
 ds.pop_back();
 sets(nums,index+1,n,ds);
}
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int>ds;
        sets(nums,0,nums.size(),ds);
        vector<vector<int>>v;
        for(auto i:st){
            v.push_back(i);
        }
        return v;
    }
};

Merge Sort

class Solution {
public:
    void merge(vector<int> &arr,int low,int mid,int high){
        vector<int> temp;
        int left=low;
        int right=mid+1;
        while(left<=mid && right<=high) {
            if(arr[left]<=arr[right]){
                temp.push_back(arr[left]);
                left++;
            }
            else{
                temp.push_back(arr[right]);
                right++;
            }
        }
        while(left<=mid) {
            temp.push_back(arr[left]);
            left++;
        }
        while(right<=high){
            temp.push_back(arr[right]);
            right++;
        }
        for(int i=low;i<=high;i++){
            arr[i]=temp[i-low];
        }
    }
    void mergeSort(int low,int high,vector<int> &nums){
        if(low>=high) return;
        int mid=(low+high)/2;
        mergeSort(low,mid,nums);
        mergeSort(mid+1,high,nums);
        merge(nums,low,mid,high);
    }
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        mergeSort(0,n-1,nums);
        return nums;
    }
};

Combinations

class Solution {
public:
    void recursion(vector<vector<int>>& ans,vector<int> &ds,vector<int> arr,int ind,int n,int k){
        if(ind==n || ds.size()==k){
            if(ds.size()==k)
            ans.push_back(ds);
            return;
        }
        // if(ds.size()==k) return ;
        recursion(ans,ds,arr,ind+1,n,k);
        ds.push_back(arr[ind]);
        recursion(ans,ds,arr,ind+1,n,k);
        ds.pop_back();
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> v;
        for(int i=1;i<=n;i++){
           v.push_back(i);
        }
        vector<vector<int>> ans;
        vector<int> ds;
        recursion(ans,ds,v,0,n,k);
        return ans;

    }
};

Combination Sum

class Solution {
public:
    void findCombination(vector<int>& arr, int target,vector<vector<int>> &ans,vector<int>&ds,int ind,int n){
          if(ind==n){
            if(target==0){
                ans.push_back(ds);
            }
            return;
          }
          if(arr[ind]<=target){
            ds.push_back(arr[ind]);
            findCombination(arr,target-arr[ind],ans,ds,ind,n);
            ds.pop_back();
          }
          findCombination(arr,target,ans,ds,ind+1,n);
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>>ans;
        vector<int>ds;
        int n=candidates.size();
        findCombination(candidates,target,ans,ds,0,n);
        return ans;
    }
};

Combination Sum II

class Solution {
public:
    void recursion(vector<vector<int>> &ans,vector<int> &ds,int ind,int target,int n,vector<int> &arr){
        if(target==0){
            ans.push_back(ds);
            return;
        }
        for(int i=ind;i<n;i++){
           if(i>ind && arr[i]==arr[i-1]) continue;
           if(arr[i]>target) break;
           ds.push_back(arr[i]);
           recursion(ans,ds,i+1,target-arr[i],n,arr);
           ds.pop_back();
        }

    }
    vector<vector<int>> combinationSum2(vector<int>& v, int target) {
        vector<vector<int>> ans;
        vector<int> ds;
        int n=v.size();
        sort(v.begin(),v.end());
        recursion(ans,ds,0,target,n,v);
        return ans;

    }
};

Combination Sum III

class Solution {
public:
    void recursion(vector<vector<int>> &ans,vector<int> &ds,int ind,int n,int k,vector<int> &arr){
        if(n==0){
            if(ds.size()==k)
            ans.push_back(ds);
            return;
        }
        for(int i=ind;i<arr.size();i++){
            if(arr[i]>n) break;
            ds.push_back(arr[i]);
            recursion(ans,ds,i+1,n-arr[i],k,arr);
            ds.pop_back();
        }

    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int>nums;
        for(int i=1;i<=9;i++){
         nums.push_back(i);
        }
        vector<vector<int>>ans;
        vector<int>ds;
        recursion(ans,ds,0,n,k,nums);
        return ans;

    }
};

Combination Sum IV

MLE

class Solution {
public:
    void recursion(vector<vector<int>>&ans,vector<int> &ds,int n,int target,int sum,vector<int>&arr){
        if(sum==target){
            ans.push_back(ds);
            return;
        }
        if(sum> target) return;
        for(int i=0;i<n;i++){
            ds.push_back(arr[i]);
            sum += arr[i];
            recursion(ans,ds,n,target,sum,arr);
            sum -= arr[i];
            ds.pop_back();

        }


    }

    int combinationSum4(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        vector<int> ds;
        int n=nums.size();
        recursion(ans,ds,n,target,0,nums);
        if(ans.size()==0) return 0;
        return ans.size();
    }
};

TLE

class Solution {
public:
    void recursion(vector<vector<int>>&ans,vector<int> &ds,int n,int target,int sum,vector<int>&arr,int &count){
        if(sum==target){
            // ans.push_back(ds);
            count++;
            return;
        }
        if(sum> target) return;
        for(int i=0;i<n;i++){
            // ds.push_back(arr[i]);
            sum += arr[i];
            recursion(ans,ds,n,target,sum,arr,count);
            sum -= arr[i];
            // ds.pop_back();

        }
    }

    int combinationSum4(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        vector<int> ds;
        int n=nums.size();
        int count=0;
        recursion(ans,ds,n,target,0,nums,count);

        return count;
    }
};

Optimized with DP

class Solution {
public:
    int solve(int target,vector<int> &dp,vector<int> &arr){
       if(target==0) return 1;
       if(target<0) return 0;
       int count=0;
       if(dp[target]!=-1) return dp[target];
       for(int i=0;i<arr.size();i++){
        count+=solve(target-arr[i],dp,arr);
       }
       dp[target]=count;
        return dp[target];
    }
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,-1);
        return solve(target,dp,nums);
    }
};

Subset Sums

more Space

class Solution {
  public:
    void recursion(vector<vector<int>> &ans, vector<int> &ds, int n, int ind, vector<int> &arr)
{
    if (ind == n)
    {
        ans.push_back(ds);
        return;
    }
    recursion(ans, ds, n, ind + 1, arr);
    ds.push_back(arr[ind]);
    recursion(ans, ds, n, ind + 1, arr);
    ds.pop_back();
}
vector<int> subsetSums(vector<int> arr, int n)
{
    vector<vector<int>> ans;
    vector<int> ds;
    vector<int> temp;
    recursion(ans, ds, n, 0, arr);
    for (int i = 0; i < ans.size(); i++)
    {
        if (ans[i].size() == 0)
        {
            temp.push_back(0);
            continue;
        }
        else
        {

            int sum = 0;
            for (int j = 0; j < ans[i].size(); j++)
            {
                sum += ans[i][j];
            }
            temp.push_back(sum);
        }
    }
    return temp;
}
};

Less Space

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    void recursion(int ind,int n,int sum,vector<int> &ans,vector<int>&arr){
        if(ind==n) {
            ans.push_back(sum);
            return;
        }
        recursion(ind+1,n,sum,ans,arr);
        recursion(ind+1,n,sum+arr[ind],ans,arr);

    }
    vector<int> subsetSums(vector<int> arr, int n) {
        // Write Your Code here
        vector<int> ans;
        recursion(0,n,0,ans,arr);
        return ans;

    }
};

//{ Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        vector<int> arr(N);
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        Solution ob;
        vector<int> ans = ob.subsetSums(arr, N);
        sort(ans.begin(), ans.end());
        for (auto sum : ans) {
            cout << sum << " ";
        }
        cout << endl;
    }
    return 0;
}
// } Driver Code Ends

Permutations

class Solution {
public:
    void recursion(vector<vector<int>> &ans,vector<int> &ds,int n,vector<int> &nums,vector<bool> &freq){
        if(ds.size()==nums.size()){
            ans.push_back(ds);
            return;
        }
        for(int i=0;i<n;i++){
           if(!freq[i]){
            ds.push_back(nums[i]);
            freq[i]=true;
            recursion(ans,ds,n,nums,freq);
            freq[i]=false;
            ds.pop_back();

           }
        }

    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> ds;
        vector<vector<int>> ans;
        int n=nums.size();
        vector<bool> freq(n+1,false);
        recursion(ans,ds,n,nums,freq);
        return ans;
    }
};

Using Swap

class Solution {
public:
    void recursion(vector<vector<int>> &ans,int ind,int n,vector<int> &arr){
        if(ind==n){
            ans.push_back(arr);
            return;
        }
        for(int i=ind;i<n;i++){
            swap(arr[i],arr[ind]);
            recursion(ans,ind+1,n,arr);
            swap(arr[i],arr[ind]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        int n=nums.size();
        recursion(ans,0,n,nums);
        return ans;
    }
};

Permutations II

class Solution {
private:
vector<int>ds;
set<vector<int>>ans;
void rsps(vector<int>& nums,vector<bool>& freq){
    if(ds.size()==nums.size()){
        ans.insert(ds);
        return;
    }
    for(int i=0;i<nums.size();i++){
        if(freq[i]);
        else{
            ds.push_back(nums[i]);
            freq[i]=true;
            rsps(nums,freq);
            freq[i]=false;
            ds.pop_back();
        }
    }
}
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
         int n=nums.size();
         vector<bool> freq(n,false);
         rsps(nums,freq);
         vector<vector<int>>v;
         for(auto i:ans){
             v.push_back(i);
         }
         return v;

    }
};

N Queens

class Solution {
public:
    bool isSafe(int row,int col,int n,vector<string> &board){
        int dupRow=row;
        int dupCol=col;
        while(row>=0 && col>=0){
            if(board[row][col]=='Q') return false;
            row--;
            col--;
        }
        row=dupRow;
        col=dupCol;
        while(col>=0){
            if(board[row][col]=='Q') return false;
            col--;
        }
        row=dupRow;
        col=dupCol;
        while(row<n && col>=0){
            if(board[row][col]=='Q') return false;
            row++;
            col--;
        }
        return true;
    }
    void solve(int col,int n,vector<string> &board,vector<vector<string>>&ans){
        if(col==n){
            ans.push_back(board);
            return;
        }
        for(int row=0;row<n;row++){
            if(isSafe(row,col,n,board)){
                board[row][col]='Q';
                solve(col+1,n,board,ans);
                board[row][col]='.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> board(n);
        string s(n,'.');
        for(int i=0;i<n;i++){
            board[i]=s;
        }
        solve(0,n,board,ans);
        return ans;
    }
};

N Queens II

class Solution {
public:
    void solve(int col,int n,vector<bool> &leftRow,vector<bool>&lowerDiagonal,vector<bool>&upperDiagonal,vector<string>&board,vector<vector<string>> &ans)
    {
        if(col==n){
            ans.push_back(board);
            return;
        }
        for(int row=0;row<n;row++){
          if(!leftRow[row] && !upperDiagonal[n-1+col-row] && !lowerDiagonal[row+col]){
            leftRow[row]=true;
            upperDiagonal[n-1+col-row]=true;
            lowerDiagonal[row+col]=true;
            board[row][col]='Q';
            solve(col+1,n,leftRow,lowerDiagonal,upperDiagonal,board,ans);
            leftRow[row]=false;
            upperDiagonal[n-1+col-row]=false;
            lowerDiagonal[row+col]=false;
            board[row][col]='.';
          }
        }
    }
    int totalNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> board(n,string(n,'.'));
        vector<bool> leftRow(n,false),lowerDiagonal(2*n-1,false),upperDiagonal(2*n-1,false);
        solve(0,n,leftRow,lowerDiagonal,upperDiagonal,board,ans);
        return ans.size();
    }
};

Optimized

class Solution {
public:
    void solve(int col,int n,vector<bool> &leftRow,vector<bool>&lowerDiagonal,vector<bool>&upperDiagonal,vector<string>&board,int &count)
    {
        if(col==n){
            count++;
            return;
        }
        for(int row=0;row<n;row++){
          if(!leftRow[row] && !upperDiagonal[n-1+col-row] && !lowerDiagonal[row+col]){
            leftRow[row]=true;
            upperDiagonal[n-1+col-row]=true;
            lowerDiagonal[row+col]=true;
            board[row][col]='Q';
            solve(col+1,n,leftRow,lowerDiagonal,upperDiagonal,board,count);
            leftRow[row]=false;
            upperDiagonal[n-1+col-row]=false;
            lowerDiagonal[row+col]=false;
            board[row][col]='.';
          }
        }
    }
    int totalNQueens(int n) {
        vector<string> board(n,string(n,'.'));
        int count=0;
        vector<bool> leftRow(n,false),lowerDiagonal(2*n-1,false),upperDiagonal(2*n-1,false);
        solve(0,n,leftRow,lowerDiagonal,upperDiagonal,board,count);
        return count;
    }
};

Sudoku Solver

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
    bool solve(vector<vector<char>> &board){
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[i].size();j++){
                if(board[i][j]=='.'){
                    for(char c='1';c<='9';c++){
                        if(isValid(board,i,j,c)){
                            board[i][j]=c;
                            if(solve(board)){
                                return true;
                            }
                            else {
                                board[i][j]='.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool isValid(vector<vector<char>> &board,int row,int col,char c){
        for(int i=0;i<9;i++){
            if(board[i][col]==c) return false;
            if(board[row][i]==c) return false;
            if(board[3*(row/3)+(i/3)][3*(col/3)+(i%3)]==c) return false;
        }
        return true;
    }
};

Sudoku Visualizer

M Coloring Problem

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    bool isSafe(int node,vector<int> adj[],vector<int> &color,int col){
        for(auto adjNode:adj[node]){
            if(color[adjNode]==col) return false;
        }
        return true;
    }
    bool solve(vector<int> adj[],int m,int n,int node,vector<int> &color){
        if(node==n) return true;
        for(int i=1;i<=m;i++){
            if(isSafe(node,adj,color,i)){
                color[node]=i;
                if(solve(adj,m,n,node+1,color)) return true;
                color[node]=0;
            }
        }
        return false;
    }
    bool graphColoring(int n, vector<pair<int, int>>& edges, int m) {
        // code here
        vector<int> adj[n];
        for(int i=0;i<edges.size();i++){
            adj[edges[i].first].push_back(edges[i].second);
            adj[edges[i].second].push_back(edges[i].first);
        }
        vector<int> color(n,0);
        return solve(adj,m,n,0,color);
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    cin.ignore();
    while (t--) {
        int n, m;
        cin >> n;
        cin.ignore(); // Ignore newline after reading n
        vector<int> arr;
        string input;
        getline(cin, input); // Read the entire line for the array elements

        stringstream ss(input);
        int number;
        while (ss >> number) {
            arr.push_back(number); // Populate the array with edge values
        }
        cin >> m;
        cin.ignore(); // Ignore newline after reading m

        int edges_count = arr.size();
        vector<pair<int, int>> edges(edges_count /
                                     2); // Correct size of the edges vector

        for (int i = 0; i < edges_count; i += 2) {
            int l1 = arr[i];
            int l2 = arr[i + 1];
            edges[i / 2] = {l1, l2}; // Properly assign the pair
        }

        Solution ob;
        cout << (ob.graphColoring(n, edges, m) ? "true" : "false")
             << endl; // Call the graph coloring function
    }
    return 0;
}

// } Driver Code Ends

Palindrome Partitioning

class Solution {
public:
   bool isPalindrome(string temp){
     int n=temp.size();
     for(int i=0;i<n/2;i++){
        if(temp[i]!=temp[n-i-1]) return false;
     }
     return true;
   }
    void solve(vector<vector<string>> &ans,vector<string> &ds,int idx,int n,string s){
        if(idx==n){
            ans.push_back(ds);
            return;
        }
        for(int i=idx;i<n;i++){
            string temp=s.substr(idx,i-idx+1);
            if(isPalindrome(temp)){
                ds.push_back(temp);
                solve(ans,ds,i+1,n,s);
                ds.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> ds;
        int n=s.size();
        solve(ans,ds,0,n,s);
        return ans;
    }
};

Palindrome Partitioning II

MLE

class Solution {
public:
    bool isPalindrome(string temp){
        int n=temp.size();
        for(int i=0;i<n/2;i++){
            if(temp[i]!=temp[n-i-1]) return false;
        }
        return true;
    }
    void solve(vector<vector<string>> &ans,vector<string> &ds,int idx,int n,string s){
        if(idx==n) {
            ans.push_back(ds);
            return;
        }
        for(int i=idx;i<n;i++){
            string temp=s.substr(idx,i-idx+1);
            if(isPalindrome(temp)){
                ds.push_back(temp);
                solve(ans,ds,i+1,n,s);
                ds.pop_back();
            }
        }
    }
    int minCut(string s) {
      vector<vector<string>> ans;
      vector<string> ds;
      int n=s.size();
      solve(ans,ds,0,n,s);
      if(ans.size()==0) return 0;
      int temp=INT_MAX;
      for(int i=0;i<ans.size();i++){
        int sz=ans[i].size();
        temp=min(temp,sz);
        for(int j=0;j<ans[i].size();j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<"\n";
      }
      return temp-1;
    }
};

TLE

class Solution {
public:
    bool isPalindrome(string temp){
        int n=temp.size();
        for(int i=0;i<n/2;i++){
            if(temp[i]!=temp[n-i-1]) return false;
        }
        return true;
    }
    void solve(int &count,vector<string> &ds,int idx,int n,string s){
        if(idx==n) {
            // ans.push_back(ds);
            int sz=ds.size();
            count=min(count,sz);
            return;
        }
        for(int i=idx;i<n;i++){
            string temp=s.substr(idx,i-idx+1);
            if(isPalindrome(temp)){
                ds.push_back(temp);
                solve(count,ds,i+1,n,s);
                ds.pop_back();
            }
        }
    }
    int minCut(string s) {
      vector<vector<string>> ans;
      vector<string> ds;
      int n=s.size();
       int temp=INT_MAX;
      solve(temp,ds,0,n,s);
    //   if(ans.size()==0) return 0;
    //
    //   for(int i=0;i<ans.size();i++){
    //     int sz=ans[i].size();
    //     temp=min(temp,sz);
    //     for(int j=0;j<ans[i].size();j++){
    //         cout<<ans[i][j]<<" ";
    //     }
    //     cout<<"\n";
    //   }
      return temp-1;
    }
};

MLE With DP

class Solution {
public:
    bool isPalindrome(string temp){
        int n=temp.size();
        for(int i=0;i<n/2;i++){
            if(temp[i]!=temp[n-i-1]) return false;
        }
        return true;
    }
    int solve(int idx,int n,string s,vector<int> &dp){
        if(idx==n)  return 0;
        if(dp[idx]!=-1) return dp[idx];
        int minCuts=INT_MAX;
        for(int i=idx;i<n;i++){
            string temp=s.substr(idx,i-idx+1);
            if(isPalindrome(temp)){
                int cuts=1+solve(i+1,n,s,dp);
                minCuts=min(minCuts,cuts);
            }
        }
        dp[idx]=minCuts;
        return dp[idx];
    }
    int minCut(string s) {
      int n=s.size();
       vector<int> dp(n+1,-1);
      return solve(0,n,s,dp)-1;
    }
};

Again MLE Even restoring string Palindromic Nature in Map

class Solution {
public:
    bool isPalindrome(string temp){
        int n=temp.size();
        for(int i=0;i<n/2;i++){
            if(temp[i]!=temp[n-i-1]) return false;
        }
        return true;
    }
    int solve(int idx,int n,string s,vector<int> &dp,unordered_map<string,bool> &mp){
        if(idx==n)  return 0;
        if(dp[idx]!=-1) return dp[idx];
        int minCuts=INT_MAX;
        for(int i=idx;i<n;i++){
            string temp=s.substr(idx,i-idx+1);
            bool palindromic=false;
            if(mp.find(temp)!=mp.end()){
                if(mp[temp])palindromic=true;

            }
            else {

                palindromic=isPalindrome(temp);
                mp[temp]=palindromic;
            }
            if(palindromic){
                int cuts=1+solve(i+1,n,s,dp,mp);
                minCuts=min(minCuts,cuts);
            }
        }
        dp[idx]=minCuts;
        return dp[idx];
    }
    int minCut(string s) {
      int n=s.size();
       vector<int> dp(n+1,-1);
       unordered_map<string,bool> mp;
      return solve(0,n,s,dp,mp)-1;
    }
};

Again MLE even with 2D DP which was storing the palindromic nature of string

class Solution {
public:
    bool isPalindrome(string s,int i,int j, vector<vector<int>> &palindrome){
        while(i<j){
            if(s[i]!=s[j]){
                palindrome[i][j]=0;
                return false;
            }
            i++;
            j--;
        }
        palindrome[i][j]=true;
        return true;
    }
    int solve(int idx,int n,string s,vector<int> &dp, vector<vector<int>> &palindrome){
        if(idx==n)  return 0;
        if(dp[idx]!=-1) return dp[idx];
        int minCuts=INT_MAX;
        for(int i=idx;i<n;i++){
            bool palindromic=false;
            if(palindrome[idx][i]!=-1) {
                if(palindrome[idx][i]==1) palindromic=true;
                else palindromic=false;
            }
            else {
                palindromic=isPalindrome(s,idx,i,palindrome);
            }
            if(palindromic){
                int cuts=1+solve(i+1,n,s,dp,palindrome);
                minCuts=min(minCuts,cuts);
            }
        }
        dp[idx]=minCuts;
        return dp[idx];
    }
    int minCut(string s) {
      int n=s.size();
       vector<int> dp(n+1,-1);
    vector<vector<int>> palindrome(n,vector<int>(n,-1));
      return solve(0,n,s,dp,palindrome)-1;
    }
};

Optimized with Bottom Up DP

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        if(n==0) return 0;
        vector<vector<bool>> palindrome(n,vector<bool> (n,false));
        for(int length=1;length<=n;length++){
            for(int i=0;i<=n-length;i++){
                  // end index
                  int j=i+length-1;
                  if(s[i]==s[j]){
                    if(length<=3){
                        palindrome[i][j]=true;
                    }
                    else {
                        palindrome[i][j]=palindrome[i+1][j-1];
                    }
                  }
            }
        }
        vector<int> dp(n,0);
        for(int i=0;i<n;i++){
            if(palindrome[0][i]) dp[i]=0;
            else {
                dp[i]=INT_MAX;
                for(int j=0;j<i;j++){
                    if(palindrome[j+1][i]){
                        dp[i] = min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        return dp[n-1];
    }
};

Rat in a Maze Problem

//{ Driver Code Starts
// Initial template for C++

#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
// User function template for C++

class Solution {
  public:
    void solve(vector<vector<int>>& mat,vector<string> &ans,string &ds,int i,int j,int n,vector<vector<bool>> &vis){
        if(i==n-1 && j==n-1){
            ans.push_back(ds);
            return;
        }
        //downward
        if(i+1<n && !vis[i+1][j] &&mat[i+1][j]==1){
            vis[i][j]=true;
            ds+='D';
            solve(mat,ans,ds,i+1,j,n,vis);
            ds.pop_back();
            vis[i][j]=false;
        }
        //left
         if(j-1>=0 && !vis[i][j-1] &&mat[i][j-1]==1){
            vis[i][j]=true;
            ds+='L';
            solve(mat,ans,ds,i,j-1,n,vis);
            ds.pop_back();
            vis[i][j]=false;
        }
        //right
         if(j+1<n && !vis[i][j+1] &&mat[i][j+1]==1){
            vis[i][j]=true;
            ds+='R';
            solve(mat,ans,ds,i,j+1,n,vis);
            ds.pop_back();
            vis[i][j]=false;
        }
        //upward
         if(i-1>=0 && !vis[i-1][j] &&mat[i-1][j]==1){
            vis[i][j]=true;
            ds+='U';
            solve(mat,ans,ds,i-1,j,n,vis);
            ds.pop_back();
            vis[i][j]=false;
        }

    }
    vector<string> findPath(vector<vector<int>> &mat) {
        // Your code goes here
        vector<string> ans;
        string ds;
        int n=mat.size();
        if(n==0 || mat[0][0]==0 || mat[n-1][n-1]==0) return ans;
        vector<vector<bool>> vis(n,vector<bool>(n,false));
        solve(mat,ans,ds,0,0,n,vis);
        return ans;
    }
};


//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> m(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> m[i][j];
            }
        }
        Solution obj;
        vector<string> result = obj.findPath(m);
        sort(result.begin(), result.end());
        if (result.size() == 0)
            cout << -1;
        else
            for (int i = 0; i < result.size(); i++)
                cout << result[i] << " ";
        cout << endl;
    }
    return 0;
}
// } Driver Code Ends

Approach 1: In-Place Modification with Backtracking

In this approach, we modify the string ds by adding the move 'D' (downward move) directly to it. After the recursive call is completed, we remove this move using pop_back() to backtrack and explore other possible paths.

if(i+1 < n && !vis[i+1][j] && mat[i+1][j] == 1) {
    vis[i][j] = true;
    ds += 'D';  // Add move to path
    solve(mat, ans, ds, i+1, j, n, vis);  // Recursive call with updated path
    ds.pop_back();  // Backtrack: remove the last move from path
    vis[i][j] = false;
}

Key Points:

•	String modification in place: The string ds is modified in place, reflecting the current state of the path.
•	Backtracking: After the recursive call, the move 'D' is removed by calling pop_back() to restore the original state of the string.
•	Clear backtracking behavior: This approach explicitly shows the backtracking process, which can help ensure correctness in algorithms that explore multiple paths.

Approach 2: Passing Modified String in Recursive Call

In this approach, instead of modifying the string ds in place, we create a new string by concatenating 'D' to ds and pass it into the recursive function directly.

if(i+1 < n && !vis[i+1][j] && mat[i+1][j] == 1) {
    vis[i][j] = true;
    solve(mat, ans, ds + 'D', i+1, j, n, vis);  // Recursive call with new string
    vis[i][j] = false;
}

Key Points:

•	No in-place modification: A new string (ds + 'D') is passed to the recursive function, leaving the original string unchanged in the current stack frame.
•	No explicit backtracking needed: Since we’re creating and passing a new string, there’s no need to explicitly backtrack or undo changes.
•	Memory overhead: This approach may create new string objects at every recursive call, potentially increasing memory usage, though in many cases, this overhead is minimal.

Why Both Are Suitable:

•	1st Approach (In-Place Modification):
•	Provides explicit control over path modifications and backtracking.
•	Commonly used in recursive algorithms that explore multiple paths.
•	2nd Approach (Passing Modified String):
•	Simplifies code by avoiding the need for backtracking.
•	Can be easier to implement when you don’t need to modify the current path object.

Both approaches will generate the correct paths for a maze or matrix traversal problem. The choice between them depends on personal preference, code clarity, or performance considerations.

Conclusion:

•	Approach 1 is suitable when you want to manage backtracking explicitly and avoid creating new objects.
•	Approach 2 is more concise but may involve slightly more memory usage due to creating new strings at each recursive step.

Permutation Sequence

class Solution {
public:
    string getPermutation(int n, int k) {
        int fact=1;
        vector<int> numbers;
        for(int i=1;i<n;i++){
            fact*=i;
            numbers.push_back(i);
        }
        numbers.push_back(n);
        string ans="";
        k--;
        while(true){
            ans+=to_string(numbers[k/fact]);
            numbers.erase(numbers.begin()+(k/fact));
            if(numbers.empty()) break;
            k%=fact;
            fact/=numbers.size();
        }
        return ans;
    }
};

Largest Time for Given Digits

class Solution {
public:
    void recursion(int ind,vector<string> &ans,vector<int>&arr){
        if(ind==arr.size()) {
            string ds="";
            for(auto it:arr){
                char x=it+'0';
                ds+=x;
            }
            ans.push_back(ds);
        }
        for(int i=ind;i<arr.size();i++){
            swap(arr[i],arr[ind]);
            recursion(ind+1,ans,arr);
            swap(arr[i],arr[ind]);
        }
        
    }
    bool isPossible(string temp){
        int a=temp[0]-'0';
        int b=temp[1]-'0';
        int c=temp[2]-'0';
        int d=temp[3]-'0';
        if(a>2) return false;
        if(b>3 && a==2) return false;
        if(c>5) return false;
        return true;
    }
    string largestTimeFromDigits(vector<int>& arr) {
        string ds="";
        vector<string>ans;
        recursion(0,ans,arr);
        sort(rbegin(ans),rend(ans));
        for(int i=0;i<ans.size();i++){
            cout<<ans[i];
            cout<<"\n";
            if(isPossible(ans[i])){
                string x=ans[i].substr(0,2);
                string y=ans[i].substr(2,2);
                return (x+':'+y);
            }
        }
        return "";                                      
    }
};