If I had downloaded your workbook first, it might have taken me a bit longer, but because I tried to replicate what I saw with a brand new Superstore workbook first, I hit upon the solution right away. Upon downloading your example, I saw the subtle complexity to the problem, but was able to use my original approach.
As for the hack, the approach you mention is not what came to mind immediately. Rather, I envisioned using the Union functionality to add a row or two for a "Grand Total" Category and then using some table calculations to sort things out. Not a very viable solution for most real-world cases, but it would probably work well for a brain-teaser! The hack you mentioned would probably be a bit more viable since it at least maintains the integrity of the data.