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

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.

&nbsp;
Example 1:

Input: digits = [8,1,9]
Output: "981"


Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"


Example 3:

Input: digits = [1]
Output: ""


&nbsp;
Constraints:


	1 &lt;= digits.length &lt;= 104
	0 &lt;= digits[i] &lt;= 9


class Solution:
	def largestMultipleOfThree(self, digits: List[int]) -> str:
		A = digits
		A.sort()
		A.reverse()

		@cache
		def DP(i, r): # max number whose remainder is r using subarray [0:i] (inclusive) 
			if i == 0:
				if A[0] % 3 == r:
					return A[0]
				else:
					return 0

			Ra = DP(i-1, r)
			Rb = [ x for j in range(3) \
				  for x in ( DP(i-1,j) * 10 + A[i] ,)
				  if x % 3 == r ]

			return max([Ra, *Rb])

		ans = DP(len(A) - 1, 0)

		if ans == 0 and 0 not in A:
			return ""
		else:
			return str(ans)
class Solution {
    public String largestMultipleOfThree(int[] digits) {
        int n=digits.length;
        Arrays.sort(digits);
        
        if(digits[digits.length-1]==0){
            return "0";
        }
        
        int sum=0;
        
        for(int i=0;i<digits.length;i++){
            sum+=digits[i];
        }
        
        if(sum%3==0){
            StringBuilder sb=new StringBuilder("");
            
            for(int i=n-1;i>=0;i--){
                sb.append(digits[i]);
            }
            
            return sb.toString();
        }else if(sum%3==1){
            int modOne=-1;
            
            for(int i=0;i<n;i++){
                if(digits[i]%3==1){
                    modOne=i;
                    break;
                }
            }
            
            if(modOne==-1){
                int []idx=new int[2];
                Arrays.fill(idx,-1);
                
                for(int i=0;i<n;i++){
                    if(digits[i]%3==2){
                        if(idx[0]==-1){
                            idx[0]=i;
                        }else{
                            idx[1]=i;
                            break;
                        }
                    }
                }
                
                if(idx[1]==-1){
                    return "";
                }else{
                    digits[idx[0]]=-1;
                    digits[idx[1]]=-1;
                }
            }else{
                digits[modOne]=-1;
            }
        }else{
            int modTwo=-1;
            
            for(int i=0;i<n;i++){
                if(digits[i]%3==2){
                    modTwo=i;
                    break;
                }
            }
            
            if(modTwo==-1){
                int []idx=new int[2];
                Arrays.fill(idx,-1);
                
                for(int i=0;i<n;i++){
                    if(digits[i]%3==1){
                        if(idx[0]==-1){
                            idx[0]=i;
                        }else{
                            idx[1]=i;
                            break;
                        }
                    }
                }
                
                if(idx[1]==-1){
                    return "";
                }else{
                    digits[idx[0]]=-1;
                    digits[idx[1]]=-1;
                }
            }else{
                digits[modTwo]=-1;
            }
        }
        
        StringBuilder sb=new StringBuilder("");
        
        for(int i=n-1;i>=0;i--){
            if(digits[i]!=-1){
                sb.append(digits[i]);
            }
            
        }
        
        if(sb.length()>0 && sb.toString().charAt(0)=='0'){
            return "0";
        }
        return sb.toString();
    }
}
class Solution {
public:

    vector<int> ans;

    void calculate(vector<int>& count,int no,vector<int>& temp){

        if(no==0){
            int flag=0,sum1=0,sum2=0,validSum=0;
            for(int j=1;j<10;j++){
                sum1+=temp[j];
                sum2+=ans[j];
                validSum+=(temp[j]*j);
            }
            if(validSum%3!=0){
                return ;
            }

            if(sum2>sum1)
                return;
            else if(sum1>sum2){
             for(int i=1;i<10;i++){
              ans[i]=temp[i];
             }
                return ;
            }
            int j=9;
            while(j>0){
                if(ans[j]<temp[j])
                {
                    flag=1;
                    break;
                }else if(ans[j]>temp[j])
                    break;
                j--;
            }
            if (flag==1){
             for(int i=1;i<10;i++){
              ans[i]=temp[i];
             }
            }
            return ;
        }

        int targetCount=count[no]-2;

        if(targetCount<0)
            targetCount=0;

        int co=count[no];

        do{
            temp[no]=co;

            calculate(count,no-1,temp);

            co--;
        }
        while(co>=targetCount);

    }

    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> count(10,0);
        int n=digits.size();
        for(int i=0;i<n;i++){
            count[digits[i]]++;
        }
        vector<int> temp(10,0);
        ans.resize(10,0);
        calculate(count,9,temp);

        string res="";
        ans[0]=count[0];
        for(int i=9;i>=0;i--){
            for(int j=1;j<=ans[i];j++){
                res+=('0'+i);
            }
        }
        if(res.size()>=2 && res[0]=='0' && res[1]=='0')
            return "0";
        return res;
    }
};
/**
 * @param {number[]} digits
 * @return {string}
 */
var largestMultipleOfThree = function(digits) {
    // highest digit first
    digits.sort((l, r) => r - l);
    
    // what is the remainder of the total sum?
    const sumRemainder = digits.reduce((a, c) => a + c, 0) % 3;
    
    if (sumRemainder) {
        let targetIndex = 0, i = digits.length - 1;
        
        // try to find what is the smallest number that can be removed
        for (; i >= 0; i--) {
            if ((digits[i] - sumRemainder) % 3 === 0) {
                targetIndex = i;
                break;
            }
        }

        if (i < 0) {
            // iterated the whole loop, couldn't find a single number to remove
            // remove everything but multiples of 3
            digits = digits.filter(v => v % 3 === 0);
        } else {
            digits.splice(targetIndex, 1);
        }
    }
    
    return (digits[0] === 0) ? '0' : digits.join('');
};
Largest Multiple of Three