Count of sub-arrays with a given sum such that the indices are in ascending order

Given an array, count the number of sub-arrays with a given sum such that the indices are in ascending order (They do not need to be continuous, but the indices of the elements of the array should be in ascending order.)

For example - Array - {1 2 3 4 5}, Sum - 5 Then {1,4} is also a valid sub array as the indices are in ascending order (1 < 4). Others are {2,3} etc.

NOTE - This question seems to be very much similar to the question of count of sub-arrays, but it becomes more complicated when it comes to the indices being in ascending order as there will be more values then. I request someone to please share a Pseudo Code for the same and if not possible, share the logic.

They're array elements, not subarrays. Subarrays have to be contiguous. {2,3} is a subarray, {1,4} is not.

Assume you had to do it with a paper and pencil. What would you do?

Quote:

---

Originally Posted by gamerrk1004

NOTE - This question seems to be very much similar to the question of count of sub-arrays, but it becomes more complicated when it comes to the indices being in ascending order as there will be more values then.

---

A brute force solution is to generate the power-set of the array viewed as a set.

https://en.wikipedia.org/wiki/Power_set

During generation, the subsets with the wanted property are selected.

Thanks for replying everyone. I understood the logic. :)