<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 {
private:
    void _largestMultipleOfThree(vector<int>& tbl, int sum, multiset<int, greater<int>>& s, string& str) {
        int i, n;
        int maxsum;
        multiset<int, greater<int>>::iterator it;
        queue<vector<int> *> q;

        n = 0;
        maxsum = -1;
        for (;;) {
            int val;
            vector<int> *erasures;
            vector<int> *new_erasures;

            if (q.size() > 0) {
                erasures = q.front();
                q.pop();
                val = erasures->size();
                if (val != n) {
                    if (maxsum != -1)
                        return;
                    maxsum = -1;
                }
                n = val;
                for (i = 0; i < n; i++) {
                    val = erasures->at(i);
                    s.erase(s.lower_bound(val));
                    --tbl[val];
                    sum -= val;
                }
            } else
                erasures = nullptr;

            for (i = 0; i < 10; i++) {
                if (tbl[i] == 0)
                    continue;

                sum -= i;
                if (sum % 3 == 0 && sum > maxsum) {
                    s.erase(s.lower_bound(i));
                    str.clear();
                    for (it = begin(s); it != end(s); ++it)
                        str += '0' + *it;
                    s.insert(i);
                    maxsum = sum;
                }
                new_erasures = erasures == nullptr
                               ? new vector<int>()
                               : new vector<int>(*erasures);
                new_erasures->push_back(i);
                q.push(new_erasures);
                sum += i;
            }

            if (erasures != nullptr) {
                for (i = 0; i < n; i++) {
                    val = erasures->at(i);
                    sum += val;
                    ++tbl[val];
                    s.insert(val);
                }
            }
        }
    }

public:
    string largestMultipleOfThree(vector<int>& digits) {
        int i, n;
        int sum;
        multiset<int, greater<int>> s;
        multiset<int, greater<int>>::iterator it;
        string res;
        vector<int> tbl;

        /*

           98866
           9886 9866 8866
           988 986 966 886 866
           98 96 88 86 66
           9 8 6

        */

        tbl = vector<int>(10);

        n = digits.size();

        sum = 0;
        for (i = 0; i < n; i++) {
            int d = digits[i];

            s.insert(d);
            ++tbl[d];
            sum += d;
        }

        if (sum % 3 == 0) {
            for (it = begin(s); it != end(s); ++it)
                res += '0' + *it;
        } else
            _largestMultipleOfThree(tbl, sum, s, res);

        if (res[0] == '0')
            res.resize(1);

        return res;
    }
};
31060