Given a list of fractions, group them so that each group sums to a whole number. This should be done in such a way to maximize the number of non-empty groups.
You may assume a solution exists. Order does not matter, both for the groups and their contents. You may output in any order.
Test Cases
| Fractions | Groups |
|---|---|
1/2, 1/2, 1/2, 1/2 |
(1/2, 1/2), (1/2, 1/2) |
1/2, 1/3, 1/6, 6/7, 8/7 |
(1/2, 1/3, 1/6), (8/7, 6/7) |
5/3, 2/3, 2/3, 1/3, 1/3, 1/3 |
(1/3, 5/3), (1/3, 2/3), (1/3, 2/3) |
9/2, 3/4, 1/12, 7/4, 2/3, 2/3, 7/12 |
(9/2, 3/4, 1/12, 2/3), (7/4, 2/3, 7/12) |
1/10, 1/5, 1/2, 7/10, 1/2 |
(1/10, 1/5, 7/10), (1/2, 1/2) |
IO
You may take fractions as a tuple or list of [numerator, denominator], and output in the same format. You can also use your language's built-in fraction type if it exists.
If there are multiple optimal solutions you may output any of them, some of them, or all of them. Do not output any non-optimal solutions.
1/10, 1/5, 1/2, 7/10, 1/2->(1/10, 1/5, 7/10), (1/2, 1/2)\$\endgroup\$(1/12, 2/3, 2/3, 7/12), (3/4, 7/4, 9/2),(1/12, 2/3, 3/4, 9/2), (2/3, 7/12, 7/4)and(1/12, 2/3, 7/4, 9/2), (2/3, 3/4, 7/12). \$\endgroup\$