A chef plans a tasting menu with one dish from each of four courses. Each dish is listed by how
far its calories are from the plan: starters[i], mains[j], sides[k] and desserts[m] (a
negative number means the dish is lighter than planned). Return the number of index choices
(i, j, k, m) for which the four numbers add up to exactly target. Dishes at different indexes
count as different choices even when their numbers are equal. If any course is empty, return 0.
Examples
Input: starters = [1, -1], mains = [0, 2], sides = [-2, 1], desserts = [1, 0], target = 0
Output: 3
Explanation: 1+0-2+1, -1+2-2+1 and -1+0+1+0 all equal 0.
Input: starters = [5], mains = [], sides = [1], desserts = [1], target = 7
Output: 0
Constraints
0 <= len(each course) <= 300-10**6 <= each number, target <= 10**6- Target complexity: about O(n^2) time, where n is the length of the longest course.
Goals
- Split a four-way choice into two two-way choices
- Tally every sum of one half in a dictionary
- Count matches with a complement lookup instead of nested loops