given a number n and a array , print all the subarrays whose sum is exactly n

general
, , , , ,
1

I want an efficient algoritlm that can be used to solve the above problem .
Thank you.

2

u can use the sum of subsets algorithm…

algo sos(pos,curr_sum,remaining_sum)

    vis[pos]=true;  
//marking the current pos as visited

    if(curr_sum+arr[pos]==req_sum)
//checks if the required sum is attained and prints that subset

        for(i=0;i<n;i++)

            if(vis[i])

                print i

        print '\n'

    else if(pos < n-1 && curr_sum+arr[pos]+arr[pos+1] <= req_sum)
//checks if the current & next position element is added then the sum does not exceed the //required sum
//truncating left subtree

        sum(pos+1,curr_sum+arr[pos],remaining_sum-arr[pos]);

    if(pos < n-1 && curr_sum+arr[pos+1] <= req_sum && curr_sum+remaining_sum-arr[pos] >= req_sum)
//checks if the current element is dropped then will the sum be able to reach the required sum
//truncating right subtree

        vis[pos]=false;
        sum(pos+1,curr_sum,remaining_sum-arr[pos]);

    vis[pos]=false;   
//marking the current position as not visited as the fxn will return to the previous call

initial call will be made using pos=0 curr_sum=0 and remaining_sum=(sum of all elements in the array)…hope this helps…:slight_smile: