The SubarraySum algorithm below solves the problem of identifying how many ways

Question

The SubarraySum algorithm below solves the problem of identifying how many ways there are to select a given total from an array. For example, in the array [1, 2, 4, 4, 7, 9, 10], there are 5 different ways to make a sum of 15: 1. [1, 4, 10] 2. [1, 4, 10] 3. [2, 4, 9] 4. [2, 4, 9] 5. [4, 4, 7] Note that the two fours are considered distinct, even though they have the same value. Answer the following questions about the SubarraySum algorithm. Input: data: array of integers with values 1-10 Input: n: size of data Input: t: positive integer Output: all of the distinct ways to select numbers from data that add up to t 1 Algorithm: SubarraySum 2 if n = 0 then 3 return 0 4 else 5 soln = 0 6 for i = 1 to n do 7 if data[i] = t then 8 Add {data[i] to soln 9 else if data[i]

Explanation / Answer

1.

line 9 says data[i] < t,

it means t is always greater than data[i]

thus, t - data[i] must always be positive.

2.

In The line 10, we are calling subarray procedure with a data array, and a sum of (t - data[i]).. Hence whatever solutions are returned from tis procedure, the each soltuion gives a sum of (t - data[i]). Now in line 11, we added data[i] in every set of the above solution, which means each solution has not started giving sum of (t - data[i]) + data[i], which is t.

Hence proved..that every element of temp, adds up to t.

3.

A = [a1, a2,..] this solution adds to t,

hence a1 < t;

so when program is running for the first time, for i=1 at line 6,

it find data[i] < t, hence it calls subArraySum method with (data(i+1.. n), t - data[i])..

Now subarray method must have returned [a2,a3...], which adds upto (t - a1), we will add data[i] i.e. a1 to this set at line 11,

and then this complete set is added to soln in line 12.

Hence proved that the solution was added during iteration with i = 1.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.