<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>

def append_if_present2(l, x, y):
    if x is None or y is None:
        return
    l.append(x+y)
def append_if_present1(l,x):
    if x is None:
        return
    l.append(x)

def custom_size(x):
    return len(x), x

def get_best(candidates):
    if candidates == []:
        return None
    else:
        return max(candidates, key=lambda x: custom_size(x))

def get_best_a(a1,b1,c1,a2,b2,c2):
    candidates = []
    append_if_present2(candidates, a1, a2)
    append_if_present2(candidates, b1, c2)
    append_if_present2(candidates, c1, b2)
    append_if_present1(candidates, a1)
    append_if_present1(candidates, a2)
    return get_best(candidates)

def get_best_b(a1,b1,c1,a2,b2,c2):
    candidates = []
    append_if_present2(candidates, a1, b2)
    append_if_present2(candidates, b1, a2)
    append_if_present2(candidates, c1, c2)
    append_if_present1(candidates, b1)
    append_if_present1(candidates, b2)
    return get_best(candidates)

def get_best_c(a1,b1,c1,a2,b2,c2):
    candidates = []
    append_if_present2(candidates, a1, c2)
    append_if_present2(candidates, b1, b2)
    append_if_present2(candidates, c1, a2)
    append_if_present1(candidates, c1)
    append_if_present1(candidates, c2)
    return get_best(candidates)

def combine(lhalf, rhalf):
    a1,b1,c1 = lhalf
    a2,b2,c2 = rhalf
    a = get_best_a(a1,b1,c1, a2,b2,c2)
    b = get_best_b(a1,b1,c1, a2,b2,c2)
    c = get_best_c(a1,b1,c1, a2,b2,c2)
    combined = a,b,c
    return combined

def single_digit(a):
    ai = int(a)
    if ai % 3 == 0:
        return a,None, None
    elif ai%3 == 1:
        return None, a, None
    else:
        return None, None, a

def organize_multiples(digits):
    D = len(digits)
    if D == 1:
        return single_digit(digits[0])
    
    middle = D//2
    lhalf = digits[:middle]
    rhalf = digits[middle:]
    lhalf_organized = organize_multiples(lhalf)
    rhalf_organized = organize_multiples(rhalf)
    return combine(lhalf_organized, rhalf_organized)


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits = sorted(digits, reverse=True)
        digits = [str(x) for x in digits]
        a,b,c = organize_multiples(digits)
        if a is None:
            return ''
        else:
            while len(a) > 1 and a[0] == '0':
                a = a[1:]
            return a
        
        
424