<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:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        #divisible by 3 if sum of digits is divisible by 3
        
        #try to take as many 9's, try to take as many 8's, 7's
        # (i,k) k%3
        # input the length at i, i+1 increased we 

        # skip or take a number.

        # the question is , how do we build the result string

        # (0,0) -> take digit at i if i-1,k -> i,k+num%3 is one more length

        def dfs(i,k):
            if i == len(digits):
                return 0 if k%3 == 0 else float('-inf')

            key = (i,k)
            if key in cache:
                return cache[key]

            take = 1+dfs(i+1,(k+digits[i])%3)
            skip = dfs(i+1,k)

            cache[key] = max(take,skip)
            return cache[key]

        digits.sort(reverse = True)
        cache = defaultdict(int)
        size = dfs(0,0)

        #backtrack
        k = 0
        res = []
        for i in range(len(digits)):
            # if size <= 0:
            #     break
            if cache[(i+1,(k+digits[i])%3)] == size-1:
                res.append(digits[i])
                size -=1
                k = (k+digits[i])%3
        
        if res and res[0] == 0:
            return '0'

        return ''.join(map(str,res))
359