Given an input array find all subarrays with given sum K

Question

Given an input array we can find a single sub-array which sums to K (given) in linear time, by keeping track of sum found so far and the start position. If the current sum becomes greater than the K we keep removing elements from start position until we get current sum <= K.

I found sample code from geeksforgeeks and updated it to return all such possible sets. But the assumption is that the input array consists of only +ve numbers.

bool subArraySum(int arr[], int n, int sum) {     int curr_sum = 0, start = 0, i;     bool found = false;      for (i = 0; i <= n; i++)     {         while (curr_sum > sum && start < i)         {             curr_sum = curr_sum - arr[start];             start++;         }          if (curr_sum == sum)         {             cout<<"Sum found in b/w indices: "<<start<<" & "<<(i-1)<<"\n";             curr_sum -= arr[start];             start++;             found = true;         }          // Add this element to curr_sum         if (i < n) {           curr_sum = curr_sum + arr[i];         }     }      return found; } 

My question is do we have such a solution for mixed set of numbers too (both positive and negative numbers)?

Answer 1

There is no linear-time algorithm for the case of both positive and negative numbers.

Since you need all sub-arrays which sum to K, time complexity of any algorithm cannot be better than size of the resulting set of sub-arrays. And this size may be quadratic. For example, any sub-array of [K, -K, K, -K, K, -K, ...], starting and ending at positive 'K' has the required sum, and there are N²/8 such sub-arrays.

Still it is possible to get the result in O(N) expected time if O(N) additional space is available.

Compute prefix sum for each element of the array and insert the pair (prefix_sum, index) to a hash map, where prefix_sum is the key and index is the value associated with this key. Search prefix_sum - K in this hash map to get one or several array indexes where the resulting sub-arrays start:

hash_map[0] = [-1] prefix_sum = 0 for index in range(0 .. N-1):   prefix_sum += array[index]   start_list = hash_map[prefix_sum - K]   for each start_index in start_list:     print start_index+1, index   start_list2 = hash_map[prefix_sum]   start_list2.append(index) 

Answer 2

Solution as given by @Evgeny Kluev coded in Java with a little explanation.

public static void main(String[] args) {     int[] INPUT = {5, 6, 1, -2, -4, 3, 1, 5};     printSubarrays(INPUT, 5); }  private static void printSubarrays(int[] input, int k) {     Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();     List<Integer> initial = new ArrayList<Integer>();     initial.add(-1);     map.put(0, initial);     int preSum = 0;      // Loop across all elements of the array     for(int i=0; i< input.length; i++) {         preSum += input[i];         // If point where sum = (preSum - k) is present, it means that between that          // point and this, the sum has to equal k         if(map.containsKey(preSum - k)) {   // Subarray found              List<Integer> startIndices = map.get(preSum - k);             for(int start : startIndices) {                 System.out.println("Start: "+ (start+1)+ "\tEnd: "+ i);             }         }          List<Integer> newStart = new ArrayList<Integer>();         if(map.containsKey(preSum)) {              newStart = map.get(preSum);         }         newStart.add(i);         map.put(preSum, newStart);     } }