.png)
Find All Subarrays with Equal Sum
Problem Statement
Given an array, find all subarrays that have the same sum (i.e., groups of subarrays where the sum is equal).
Example Input
arr = [1, 2, 1, 2, 1]
Expected Output (Grouped by Equal Sum)
Sum = 1 → [1], [1], [1]
Sum = 2 → [2], [2]
Sum = 3 → [1,2], [2,1], [1,2], [2,1]
Sum = 4 → [1,2,1], [2,1,2]
Sum = 5 → [1,2,1,2], [2,1,2,1]
Sum = 7 → [1,2,1,2,1]
Approach 1: Brute Force
Idea
Generate all subarrays, compute sum, group by sum.
C
#include
int main(){
int arr[] = {1,2,1,2,1};
int n = 5;
for(int i=0;iC++
#include
#include
using namespace std;
int main(){
vector arr = {1,2,1,2,1};
int n = arr.size();
for(int i=0;iJavaclass Main {
public static void main(String[] args){
int[] arr = {1,2,1,2,1};
int n = arr.length;
for(int i=0;iPythonarr = [1,2,1,2,1]
n = len(arr)
for i in range(n):
for j in range(i,n):
s = 0
sub = []
for k in range(i,j+1):
s += arr[k]
sub.append(arr[k])
print("Subarray:", sub, "| Sum =", s)
JavaScriptlet arr = [1,2,1,2,1];
let n = arr.length;
for(let i=0;iOutput(Prints every subarray with its sum)Subarray: [1] | Sum = 1
Subarray: [1, 2] | Sum = 3
Subarray: [1, 2, 1] | Sum = 4
Subarray: [1, 2, 1, 2] | Sum = 6
Subarray: [1, 2, 1, 2, 1] | Sum = 7
Subarray: [2] | Sum = 2
Subarray: [2, 1] | Sum = 3
Subarray: [2, 1, 2] | Sum = 5
Subarray: [2, 1, 2, 1] | Sum = 6
Subarray: [1] | Sum = 1
Subarray: [1, 2] | Sum = 3
Subarray: [1, 2, 1] | Sum = 4
Subarray: [2] | Sum = 2
Subarray: [2, 1] | Sum = 3
Subarray: [1] | Sum = 1Approach 2: Prefix Sum (Better)IdeaUse prefix array to calculate sum in O(1), group by sum.C++#include
#include
#include
using namespace std;
int main(){
vector arr = {1,2,1,2,1};
int n = arr.size();
vector prefix(n+1,0);
for(int i=0;i>> mp;
for(int i=0;i sub(arr.begin()+i, arr.begin()+j+1);
mp[sum].push_back(sub);
}
}
for(auto &p: mp){
cout<<"Sum = "< ";
for(auto &v: p.second){
cout<<"[";
for(int x:v) cout<Javaimport java.util.*;
class Main {
public static void main(String[] args){
int[] arr = {1,2,1,2,1};
int n = arr.length;
int[] prefix = new int[n+1];
for(int i=0;i>> map = new HashMap<>();
for(int i=0;i sub = new ArrayList<>();
for(int k=i;k<=j;k++) sub.add(arr[k]);
map.putIfAbsent(sum, new ArrayList<>());
map.get(sum).add(sub);
}
}
for(int s: map.keySet()){
System.out.println("Sum = " + s + " -> " + map.get(s));
}
}
}
Pythonfrom collections import defaultdict
arr = [1,2,1,2,1]
n = len(arr)
prefix = [0]*(n+1)
for i in range(n):
prefix[i+1] = prefix[i] + arr[i]
mp = defaultdict(list)
for i in range(n):
for j in range(i,n):
s = prefix[j+1] - prefix[i]
mp[s].append(arr[i:j+1])
for s in mp:
print("Sum =", s, "->", mp[s])
JavaScriptlet arr = [1,2,1,2,1];
let n = arr.length;
let prefix = Array(n+1).fill(0);
for(let i=0;i", v);
}
Output(Grouped by equal sum)
Sum = 1 → [1], [1], [1]
Sum = 2 → [2], [2]
Sum = 3 → [1,2], [2,1], [1,2], [2,1]
Sum = 4 → [1,2,1], [1,2,1]
Sum = 5 → [2,1,2]
Sum = 6 → [1,2,1,2], [2,1,2,1]
Sum = 7 → [1,2,1,2,1]Approach 3: Frequency Concept (Count Only)IdeaCount how many subarrays share equal sum using prefix frequency.C++#include
#include
using namespace std;
int main(){
int arr[] = {1,2,1,2,1};
int n = 5;
unordered_map freq;
freq[0] = 1;
int prefix = 0, count = 0;
for(int i=0;iJavaimport java.util.*;
class Main {
public static void main(String[] args){
int[] arr = {1,2,1,2,1};
Map map = new HashMap<>();
map.put(0,1);
int prefix = 0, count = 0;
for(int x: arr){
prefix += x;
count += map.getOrDefault(prefix,0);
map.put(prefix, map.getOrDefault(prefix,0)+1);
}
System.out.println(count);
}
}
Pythonfrom collections import defaultdict
arr = [1,2,1,2,1]
freq = defaultdict(int)
freq[0] = 1
prefix = 0
count = 0
for x in arr:
prefix += x
count += freq[prefix]
freq[prefix] += 1
print(count)
JavaScriptlet arr = [1,2,1,2,1];
let map = new Map();
map.set(0,1);
let prefix = 0, count = 0;
for(let x of arr){
prefix += x;
count += map.get(prefix) || 0;
map.set(prefix, (map.get(prefix)||0)+1);
}
console.log(count);
Output (Important)Grouped Subarrays by Sum:
1 → [1], [1], [1]
2 → [2], [2]
3 → [1,2], [2,1], [1,2], [2,1]
4 → [1,2,1], [2,1,2]
5 → [1,2,1,2], [2,1,2,1]
7 → [1,2,1,2,1]
Next Problem Partition Array into K Equal Sum Subsets.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
