CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Junior Member
Join Date
Jan 2020
Posts
5

## 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.

2. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,627

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

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?

3. Member +
Join Date
Feb 2017
Posts
639

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

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.
Last edited by wolle; April 6th, 2020 at 05:42 AM.

4. Junior Member
Join Date
Jan 2020
Posts
5

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

Thanks for replying everyone. I understood the logic.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•