Find subarrays with given sum in an array

Given an array A with length N, the task is to print all possible subarrays whose sum is equals to a given number " sum".

Input: {1, 2, 3}, sum = 3
Output: {1,2}, {3}

1) Using three loops in O(n^3) time

We can simply solve this problem in O(n^3) time by finding all possible subarrays of the given array. In this approach we will iterate through each element arr[i] of the array using outer loop, the second inner loop will determine the to-from boundary for "i" to "j" and finally the third inner loop will ultimately print the elements between "i" to "j".

While generating a subarray in third inner loop we will keep on adding elements of the subarray, if any of these subarrays have sum equals to the given "sum" we will simply print that subarray.

The above given array will have following subarrays: {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3} - As you can see 1 is repeated 3 times, 2 - 4 times and 3 - 3 times, we can find total number of subarrays of an array with size n with formula n*(n+1)/2, hence 3*4/2 = 3*2 = 6.

package com.cd.array;

public class PrintAllSubarrays {

	private static int[] arr = {1, 2, 3};

	private static void printSubArrays(int[] arr, int rs) {

		for (int i = 0; i < arr.length; i++) {
			for (int j = i; j < arr.length; j++) {
				int k = i;
				int sum = 0;

				String arrElements = "";
				while (k <= j) {
					sum += arr[k];
					arrElements += arr[k] + ",";
					k++;
				}
				if (rs == sum)
					System.out.println(arrElements);
			}
		}
	}

	public static void main(String[] args) {
		printSubArrays(arr, 3);
	}
}
Output: The output of above example will be something like this:

1,2,
3


2) Optimised solution

We can print all subarrays with sum equals to a given number in O(n) time using two extra variables, one to hold sumSoFar and second lastSumIndex to hold the last index of sumSoFar.

The idea is to keep adding to sumSoFar at each element of the array, if the element is equals to the given sum print element, if element+sumSoFar is equals to the given sum print array from lastSumIndex to current index, else if element + sumSoFar is greater than the given sum keep reducing sumSoFar until its less than the given sum by sumSoFar-arr[lastSumIndex] while increasing lastSumIndex++.
package com.cd.array;

public class SubArraySumOpt {

	private static int[] arr = {1, 2, 3};

	private static void printSubArrays(int[] arr, int rs) {

		int sumSoFar = 0;

		int lastSumIndex = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == rs)
				System.out.println(arr[i]);

			sumSoFar += arr[i];
			if (sumSoFar == rs) {
				printArray(arr, lastSumIndex, i);
				System.out.println();
			}
			while (sumSoFar > rs) {
				sumSoFar -= arr[lastSumIndex];
				lastSumIndex++;
			}
		}
	}

	private static void printArray(int[] arr, int start, int end) {
		for (int i = start; i <= end; i++)
			System.out.print(arr[i] + ",");
	}

	public static void main(String[] args) {
		printSubArrays(arr, 3);
	}
}
Output: The output of above example will be something like this:

1,2,
3