Largest Multiple of Three

Hard

Given an array nums of digits (each 0-9), form the largest possible multiple of three by concatenating some of the digits, using each at most once. Return that number as an integer. If no non-empty selection is a multiple of three, return -1. If the largest value you can form is 0 (only zeros usable), return 0.

Example 1

Input:  nums = [8,1,9]
Output: 981

Example 2

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

Example 3

Input:  nums = [1]
Output: -1

Constraints

• 1 <= nums.length <= 7
• 0 <= nums[i] <= 9