<p>Given an array of digits <code>digits</code>, return <em>the largest multiple of <strong>three</strong> that can be formed by concatenating some of the given digits in <strong>any order</strong></em>. If there is no answer return an empty string.</p>

<p>Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> digits = [8,1,9]
<strong>Output:</strong> &quot;981&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> digits = [8,6,7,1,0]
<strong>Output:</strong> &quot;8760&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> digits = [1]
<strong>Output:</strong> &quot;&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= digits.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= digits[i] &lt;= 9</code></li>
</ul>

class Solution {
public:
    // int f(int i,int rem,vector<int>& digits){
    //     int n=digits.size();
    //     if(i==n){
    //         if(rem==0) return 0;
    //         return -1e9;
    //     }
    //     int pick=f(i+1,(digits[i]+rem)%3,digits)+1;
    //     int notpick=f(i+1,rem%3,digits);
    //     return max(pick,notpick);
    // }
    string largestMultipleOfThree(vector<int>& digits) {
        sort(digits.rbegin(),digits.rend());
        int n=digits.size();
        vector<vector<int>>dp(n+1,vector<int>(3,0));
        for(int i=n;i>=0;i--){
            for(int j=0;j<=2;j++){
                if(i==n){
                    if(j==0) dp[i][j]=0;
                    else dp[i][j]=-1e9;
                }else{
                int pick=dp[i+1][(digits[i]+j)%3]+1;
                int notpick=dp[i+1][j];
                dp[i][j]=max(pick,notpick);
                }
            }
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=2;j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        string s;
        int ind1=0,ind2=0;
        
        while(ind1!=n){
            cout<<"hi"<<endl;
            int pick=dp[ind1+1][(digits[ind1]+ind2)%3]+1;
            int notpick=dp[ind1+1][ind2];
            cout<<pick<<endl;
            if(dp[ind1][ind2]==pick){
                s+=to_string(digits[ind1]);
                ind2=(digits[ind1]+ind2)%3;
                ind1=ind1+1;
            }else{
                ind1=ind1+1;
            }
        }
        int ind=s.size()-1;
        for(int i=0;i<s.size();i++){
            if(s[i]!='0'){
                ind=i;
                break;
            }
        }
        string newS="";
        for(int i=ind;i<s.size();i++){
            newS+=s[i];
        }
        return newS;
    }
};
33940