**Editorialist:** Harshit Kumar

**PREREQUISITES:**

- Basic Arithmetic

**PROBLEM LINK:**

**PROBLEM IN SHORT:**

Given a sequence of N non-zero positive numbers, find the number of ways of expressing T as the sum of four elements of S.

**SOLUTION:**

● At first, we will make a table of every unique number and its frequency.

● Now Imagine you have 4 boxes, A, B, C, D. we will fill these boxes with numbers such that A>=B>=C>=D.

● Try filling the boxes with numbers such that the above condition is satisfied, and they add up to the required sum. When a valid combination if found, use the frequency table to find the count.

● After adding up the numbers there could only be three possibilities, 1) Sum>T: we’ll change the least significant number that can be reduced (not minimum) with

the highest number in the sequence that is less than the given number. 2) Sum<T: we’ll change the most significant number with the highest number in the sequence that is less than the given number and maximize the other numbers under given conditions(A>=B>=C>=D). 3) Sum=T: Find the count using frequency table.

**Example:** Let’s take subtask 1: S = (2, 1, 1, 1, 2, 1, 2, 2, 1) and T = 6

Frequency Table:

1 -> Count=5

2 -> Count=4

Now fill the boxes:

2,2,2,2 -> exceed sum

2,2,2,1 ->exceed sum

2,2,1,1 -> **possible! Number of ways=5C2 * 4C2 = 60** (number of ways of choosing 2 items out of 5 items * number of ways of choosing 2 items out of 4 items).

2,1,1,1 -> less than sum

1,1,1,1 -> less than sum

No other possibility

**Answer = 60.**

Since the array only consists of 1s and 2s you can also do this question by observation.

there is only 1 way: using two 2s and two 1s. thus, the number of ways =

4C2 * 5C2 = 60.

**Example:** Let’s take subtask 3: S = (1, 3, 2, 1, 1, 3, 4, 2, 2) and T = 8

Frequency Table:

1 -> Count=3

2 -> Count=3

3 -> Count=2

4 -> Count=1

4,3,3,_ -> exceeds sum.

4,3,2,_ -> exceeds sum.

4,3,1,1 -> exceed sum.

4,2,2,2 -> exceed sum.

4,2,2,1 -> exceed sum.

4,2,1,1-> **possible! Number of ways=1C1 * 3C1 * 3C2 = 9.**

4,1,1,1-> less than sum.

3,3,2,2 -> exceeds sum.

3,3,2,1 -> exceeds sum.

3,3,1,1 -> **possible! Number of ways=2C2 * 3C2 = 3.**

3,2,2,2 -> exceeds sum.

3,2,2,1 -> **possible! Number of ways=2C1 * 3C2 * 3C1 = 18.**

3,2,1,1 - > less than sum.

2,2,2,1 -> less than sum.

**Answer =** 9 + 3 +18 = 30

**Bonus:** Do the 2nd part yourself.

Hope that helped.