Find subarray with given sum using Nested loop
The idea is to consider all subarrays one by one and check the sum of every subarray. Following program implements the given idea.
Run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i.
Follow the steps given below to implement the approach:
- Traverse the array from start to end.
- From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.
- For every index in inner loop update currentSum = currentSum + arr[j]
- If the currentSum is equal to the given sum then print the subarray.
Below is the implementation of the above approach.
/* A simple program to print subarray
with sum as given sum */
#include <bits/stdc++.h>
using namespace std;
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
cout << "Sum found at indexes " << i << endl;
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
cout << "Sum found between indexes "
<< i << " and " << j << endl;
return;
}
}
}
}
cout << "No subarray found";
return;
}
// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
// This code is contributed
// by rathbhupendra
/* A simple program to print
subarray with sum as given sum */
#include <stdio.h>
/* Returns true if the there is a subarray
of arr[] with a sum equal to 'sum'
otherwise returns false. Also, prints
the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
printf("Sum found at indexe %d ", i);
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
printf("Sum found between indexes %d "
"and %d",
i, j);
return;
}
}
}
}
printf("No subarray found");
return;
}
// Driver program to test above function
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
public class SubarraySum {
/* Returns true if the there is a
subarray of arr[] with a sum equal to
'sum' otherwise returns false.
Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
System.out.println("Sum found at indexe "
+ i);
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
System.out.println(
"Sum found between indexes " + i
+ " and " + j);
return;
}
}
}
}
System.out.println("No subarray found");
return;
}
public static void main(String[] args)
{
SubarraySum arraysum = new SubarraySum();
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
// This code has been contributed by Mayank
// Jaiswal(mayank_24)
# A simple program to print subarray with sum as given sum
# Returns true if the there is a subarray of arr[] with sum equal to 'sum' otherwise returns false. Also, prints the result
def subArraySum(arr, n, sum):
# Pick a starting point
for i in range(0,n):
currentSum = arr[i]
if(currentSum == sum):
print("Sum found at indexes",i)
return
else:
# Try all subarrays starting with 'i'
for j in range(i+1,n):
currentSum += arr[j]
if(currentSum == sum):
print("Sum found between indexes",i,"and",j)
return
print("No Subarray Found")
# Driver Code
if __name__ == "__main__":
arr = [15,2,4,8,9,5,10,23]
n = len(arr)
sum = 23
subArraySum(arr, n, sum)
# This code is contributed by ajaymakvana
using System;
public class HelloWorld
{
/* Returns true if the there is a subarray of arr[] with a sum equal to
'sum' otherwise returns false. Also, prints the result */
public static void subArraySum(int[] arr, int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
Console.WriteLine("Sum found at indexe " + i);
return;
} else
{
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
Console.WriteLine("Sum found between indexes " + i + " and " + j);
return;
}
}
}
}
Console.WriteLine("No subarray found");
return;
}
public static void Main(string[] args) {
int[] arr = {15, 2, 4, 8, 9, 5, 10, 23};
int n = arr.Length;
int sum = 23;
subArraySum(arr, n, sum);
}
}
// This code is contributed by ajaymakavana.
/* A simple program to print subarray
with sum as given sum */
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
function subArraySum( arr, n, sum)
{
// Pick a starting point
for (let i = 0; i < n; i++) {
let currentSum = arr[i];
if (currentSum == sum) {
console.log("Sum found at indexes " +i);
return;
}
else {
// Try all subarrays starting with 'i'
for (let j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
console.log("Sum found between indexes "
+ i + " and " +j);
return;
}
}
}
}
console.log("No subarray found");
return;
}
let arr = [15, 2, 4, 8, 9, 5, 10, 23 ];
let n = arr.length;
let sum = 23;
subArraySum(arr, n, sum);
// This code is contributed by garg28harsh.
Output
Sum found between indexes 1 and 4
Time Complexity: O(N2), Trying all subarrays from every index, used nested loop for the same
Auxiliary Space: O(1).
Find Subarray with given sum | Set 1 (Non-negative Numbers)
Given an array arr[] of non-negative integers and an integer sum, find a subarray that adds to a given sum.
Note: There may be more than one subarray with sum as the given sum, print first such subarray.
Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Explanation: Sum of elements between indices 2 and 4 is 20 + 3 + 10 = 33Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4
Explanation: Sum of elements between indices 1 and 4 is 4 + 0 + 0 + 3 = 7Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
Explanation: There is no subarray with 0 sum