Solution Explanation: Largest Multiple of Three

This problem asks to find the largest multiple of 3 that can be formed by concatenating some digits from a given array. The solution uses a combination of greedy approach, dynamic programming, and backtracking.

1. Greedy Approach & Sorting:

The core idea is that to maximize the resulting number, we want to use as many digits as possible. We start by sorting the digits in descending order. This ensures that when we have choices, we prioritize larger digits.

2. Dynamic Programming:

We employ dynamic programming to efficiently explore the space of possible digit combinations. We define a DP table f[i][j] where:

• i represents the index of the current digit being considered (0-indexed).
• j represents the remainder when the sum of the selected digits is divided by 3 (0, 1, or 2).
• f[i][j] stores the maximum number of digits selected up to index i such that the remainder is j.

The recurrence relation is:

f[i][j] = max(f[i-1][j], f[i-1][(j - digits[i] % 3 + 3) % 3] + 1)

This means that for the i-th digit, we have two choices:

• Don't include it: The maximum number of digits remains the same as f[i-1][j].
• Include it: The remainder updates to (j - digits[i] % 3 + 3) % 3, and we add 1 to the count of selected digits.

3. Backtracking:

After computing the DP table, f[n][0] (where n is the number of digits) indicates the maximum number of digits that can form a multiple of 3. If f[n][0] is 0 or less, no solution exists.

Otherwise, we backtrack through the DP table to reconstruct the solution. Starting from f[n][0], we trace back to find which digits were included to reach this state. The choice is made based on whether including or excluding the current digit yields the optimal solution. Because we sorted the digits, the backtracking process implicitly constructs the lexicographically largest solution.

4. Handling Leading Zeros:

Finally, the code handles leading zeros by removing them from the result string.

Time and Space Complexity:

• Time Complexity: O(n log n) due to the sorting step. The DP table computation is O(n), and backtracking is also O(n).
• Space Complexity: O(n) to store the DP table.

Code Examples (Python):

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort(reverse=True)
        n = len(digits)
        f = [([-float('inf')] * 3) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1)
 
        if f[n][0] <= 0:
            return ""
 
        res = []
        i, j = n, 0
        while i > 0:
            if f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1 == f[i][j]:
                res.append(digits[i - 1])
                j = (j - digits[i - 1] % 3 + 3) % 3
            i -= 1
 
        res.sort(reverse=True) #Sorting to get the largest number, not necessary in this example
        ans = "".join(map(str, res))
        return ans.lstrip('0') or ""
 

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, implementing the dynamic programming and backtracking steps. The core logic remains consistent across all languages.