Generating All Subarrays in C: Complete Guide

Generating All Subarrays in C: A Comprehensive Tutorial

Generating all subarrays of an array is a fundamental algorithmic problem that appears frequently in coding interviews and competitive programming. A subarray is a contiguous sequence of elements within an array. Understanding how to generate all subarrays efficiently is essential for solving problems involving ranges, sliding windows, and dynamic programming.

This tutorial provides an in-depth exploration of generating all subarrays in C: problem understanding, iterative and recursive approaches, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is a Subarray?

A subarray is a contiguous portion of an array. For an array of size n, there are n × (n + 1) / 2 possible subarrays.

Example:

text

Array: [1, 2, 3] Subarrays: [1], [1, 2], [1, 2, 3] [2], [2, 3] [3] Total: 3 × 4 / 2 = 6 subarrays

Subarray vs. Subsequence vs. Subset

Concept	Definition	Order Preserved?	Contiguous?
Subarray	Contiguous portion	Yes	Yes
Subsequence	Not necessarily contiguous	Yes	No
Subset	Any selection	No	No

Why Generate All Subarrays?

• Maximum subarray sum: Kadane’s algorithm foundation.
• Sliding window problems: Subarray-based optimizations.
• Range queries: Prefix sums and segment trees.
• Interview preparation: Common coding problem.
• Data analysis: Contiguous segment processing.

Number of Subarrays

For an array of size n:

• Number of subarrays = n × (n + 1) / 2
• For n = 3: 6 subarrays
• For n = 4: 10 subarrays
• For n = 5: 15 subarrays

---

Syntax & Core Mechanics

Approach 1: Iterative (Triple Nested Loops)

The most straightforward approach: fix starting index i, ending index j, and print elements from i to j.

Time complexity: O(n³)
Space complexity: O(1) for printing, O(n) for storing

c

#include <stdio.h> void printAllSubarrays(const int arr[], int n) { /* Fix starting index */ for (int i = 0; i < n; i++) { /* Fix ending index */ for (int j = i; j < n; j++) { /* Print subarray from i to j */ printf("["); for (int k = i; k <= j; k++) { printf("%d", arr[k]); if (k < j) printf(", "); } printf("]"); if (!(i == n - 1 && j == n - 1)) printf(", "); } } printf("\n"); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("All subarrays:\n"); printAllSubarrays(arr, n); return 0; }

Expected output:

text

All subarrays: [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

Approach 2: Iterative (Optimized — Two Loops)

Instead of a third loop, extend the subarray incrementally.

Time complexity: O(n²)
Space complexity: O(1)

c

#include <stdio.h> void printAllSubarraysOptimized(const int arr[], int n) { for (int i = 0; i < n; i++) { printf("["); for (int j = i; j < n; j++) { printf("%d", arr[j]); if (j < n - 1) printf(", "); /* Print current subarray */ printf("]"); if (j < n - 1 || i < n - 1) printf(", "); if (j < n - 1) printf("["); } } printf("\n"); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("All subarrays (optimized):\n"); printAllSubarraysOptimized(arr, n); return 0; }

Better implementation:

c

#include <stdio.h> void printAllSubarraysTwoLoops(const int arr[], int n) { int first = 1; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (!first) printf(", "); first = 0; printf("["); for (int k = i; k <= j; k++) { printf("%d", arr[k]); if (k < j) printf(", "); } printf("]"); } } printf("\n"); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printAllSubarraysTwoLoops(arr, n); return 0; }

Expected output:

text

[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

Approach 3: Recursive

Use recursion to generate subarrays starting from each index.

c

#include <stdio.h> /* Recursively extend subarray from start to end */ void generateFromStart(const int arr[], int n, int start, int end, int current[], int currentSize, int *first) { if (end == n) return; /* Add current element to subarray */ current[currentSize] = arr[end]; /* Print current subarray */ if (!*first) printf(", "); *first = 0; printf("["); for (int i = 0; i <= currentSize; i++) { printf("%d", current[i]); if (i < currentSize) printf(", "); } printf("]"); /* Recursively extend */ generateFromStart(arr, n, start, end + 1, current, currentSize + 1, first); } /* Generate subarrays for each starting index */ void generateAll(const int arr[], int n, int start, int *first) { if (start == n) return; int current[100]; /* Buffer for current subarray */ generateFromStart(arr, n, start, start, current, 0, first); generateAll(arr, n, start + 1, first); } int main(void) { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); int first = 1; printf("All subarrays (recursive):\n"); generateAll(arr, n, 0, &first); printf("\n"); return 0; }

Expected output:

text

All subarrays (recursive): [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

---

Full Practical Code Example with Explanation

This program demonstrates all subarray generation approaches with a complete implementation using dynamic memory for storing subarrays.

Program: Subarray Generator and Analyzer

c

/** * subarray_generator.c * Generates all subarrays using iterative and recursive approaches. * Includes storage, display, and analysis of subarrays. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #define MAX_LINE_LEN 100 #define MAX_SUBARRAYS 1000 /* Structure to hold a subarray */ typedef struct { int *elements; int size; int startIndex; int endIndex; int sum; } Subarray; /* Structure to hold all subarrays */ typedef struct { Subarray *items; int count; int capacity; } SubarrayCollection; /* Function prototypes */ SubarrayCollection *createCollection(int capacity); void freeCollection(SubarrayCollection *collection); int addSubarray(SubarrayCollection *collection, const int arr[], int start, int end); void generateIterative(const int arr[], int n, SubarrayCollection *collection); void generateRecursiveHelper(const int arr[], int n, int start, int end, SubarrayCollection *collection); void generateRecursive(const int arr[], int n, SubarrayCollection *collection); void displaySubarrays(const SubarrayCollection *collection); void analyzeSubarrays(const SubarrayCollection *collection); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void displaySubarray(const Subarray *sub); int main(void) { int choice; char buffer[MAX_LINE_LEN]; int arr[MAX_LINE_LEN]; int n = 0; printf("=== Subarray Generator and Analyzer ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Enter Array\n"); printf("2. Generate All Subarrays (Iterative)\n"); printf("3. Generate All Subarrays (Recursive)\n"); printf("4. Analyze Subarrays\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: { int size; if (readInteger("Enter array size (1-20): ", &size) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (size < 1 || size > 20) { printf("Size must be 1-20.\n"); break; } printf("Enter %d elements:\n", size); for (int i = 0; i < size; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); size = i; break; } } n = size; printf("Array: "); printArray(arr, n); break; } case 2: { if (n == 0) { printf("Please enter an array first.\n"); break; } int maxSubarrays = n * (n + 1) / 2 + 1; SubarrayCollection *collection = createCollection(maxSubarrays); if (collection == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } generateIterative(arr, n, collection); printf("\n=== All Subarrays (Iterative) ===\n"); displaySubarrays(collection); freeCollection(collection); break; } case 3: { if (n == 0) { printf("Please enter an array first.\n"); break; } int maxSubarrays = n * (n + 1) / 2 + 1; SubarrayCollection *collection = createCollection(maxSubarrays); if (collection == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } generateRecursive(arr, n, collection); printf("\n=== All Subarrays (Recursive) ===\n"); displaySubarrays(collection); freeCollection(collection); break; } case 4: { if (n == 0) { printf("Please enter an array first.\n"); break; } int maxSubarrays = n * (n + 1) / 2 + 1; SubarrayCollection *collection = createCollection(maxSubarrays); if (collection == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } generateIterative(arr, n, collection); analyzeSubarrays(collection); freeCollection(collection); break; } case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Creates a collection with initial capacity */ SubarrayCollection *createCollection(int capacity) { SubarrayCollection *collection = malloc(sizeof(SubarrayCollection)); if (collection == NULL) return NULL; collection->items = malloc(capacity * sizeof(Subarray)); if (collection->items == NULL) { free(collection); return NULL; } collection->count = 0; collection->capacity = capacity; return collection; } /* Frees the collection */ void freeCollection(SubarrayCollection *collection) { if (collection == NULL) return; for (int i = 0; i < collection->count; i++) { free(collection->items[i].elements); } free(collection->items); free(collection); } /* Adds a subarray to the collection */ int addSubarray(SubarrayCollection *collection, const int arr[], int start, int end) { if (collection->count >= collection->capacity) { return -1; /* Collection full */ } int size = end - start + 1; Subarray *sub = &collection->items[collection->count]; sub->elements = malloc(size * sizeof(int)); if (sub->elements == NULL) { return -1; } sub->size = size; sub->startIndex = start; sub->endIndex = end; sub->sum = 0; for (int i = 0; i < size; i++) { sub->elements[i] = arr[start + i]; sub->sum += sub->elements[i]; } collection->count++; return 0; } /* Generates all subarrays iteratively */ void generateIterative(const int arr[], int n, SubarrayCollection *collection) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { addSubarray(collection, arr, i, j); } } } /* Recursive helper to generate subarrays from a fixed start */ void generateRecursiveHelper(const int arr[], int n, int start, int end, SubarrayCollection *collection) { if (end >= n) return; addSubarray(collection, arr, start, end); generateRecursiveHelper(arr, n, start, end + 1, collection); } /* Generates all subarrays recursively */ void generateRecursive(const int arr[], int n, SubarrayCollection *collection) { if (n == 0) return; for (int start = 0; start < n; start++) { generateRecursiveHelper(arr, n, start, start, collection); } } /* Displays all subarrays */ void displaySubarrays(const SubarrayCollection *collection) { for (int i = 0; i < collection->count; i++) { displaySubarray(&collection->items[i]); if (i < collection->count - 1) printf(", "); } printf("\n\nTotal: %d subarrays\n", collection->count); } /* Displays a single subarray */ void displaySubarray(const Subarray *sub) { printf("["); for (int i = 0; i < sub->size; i++) { printf("%d", sub->elements[i]); if (i < sub->size - 1) printf(", "); } printf("]"); } /* Analyzes subarrays (min/max sum, etc.) */ void analyzeSubarrays(const SubarrayCollection *collection) { if (collection->count == 0) { printf("No subarrays to analyze.\n"); return; } int maxSum = collection->items[0].sum; int minSum = collection->items[0].sum; int maxSumIndex = 0; int minSumIndex = 0; for (int i = 1; i < collection->count; i++) { if (collection->items[i].sum > maxSum) { maxSum = collection->items[i].sum; maxSumIndex = i; } if (collection->items[i].sum < minSum) { minSum = collection->items[i].sum; minSumIndex = i; } } printf("\n=== Subarray Analysis ===\n"); printf("Total subarrays: %d\n", collection->count); printf("\nMaximum sum subarray: "); displaySubarray(&collection->items[maxSumIndex]); printf(" (sum = %d)\n", maxSum); printf("Minimum sum subarray: "); displaySubarray(&collection->items[minSumIndex]); printf(" (sum = %d)\n", minSum); } /* Prints an array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Subarray Generation

1. Iterative: Triple nested loops (or two loops with incremental printing).
2. Recursive: Recursion extends subarray from each start index.
3. Storage: Subarray and SubarrayCollection structures store subarrays.
4. Analysis: Finds max/min sum subarrays.
5. Memory management: Frees all allocated memory.

Expected Output (sample run)

text

=== Subarray Generator and Analyzer === --- Menu --- 1. Enter Array 2. Generate All Subarrays (Iterative) 3. Generate All Subarrays (Recursive) 4. Analyze Subarrays 5. Exit Enter choice: 1 Enter array size (1-20): 3 Enter 3 elements: Element 0: 1 Element 1: 2 Element 2: 3 Array: [1, 2, 3] --- Menu --- ... Enter choice: 2 === All Subarrays (Iterative) === [1], [1, 2], [1, 2, 3], [2], [2, 3], [3] Total: 6 subarrays --- Menu --- ... Enter choice: 4 === Subarray Analysis === Total subarrays: 6 Maximum sum subarray: [1, 2, 3] (sum = 6) Minimum sum subarray: [1] (sum = 1)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

An empty array has no subarrays.

c

int arr[] = {}; printAllSubarrays(arr, 0); // No output

Solution: Handle n == 0 separately.

2. Single Element

An array with one element has exactly one subarray.

c

int arr[] = {5}; // Subarrays: [5]

3. Duplicate Elements

Duplicate values produce distinct subarrays (by position).

c

int arr[] = {1, 1}; // Subarrays: [1], [1, 1], [1] (3 subarrays, all distinct by position)

4. Large Arrays

Number of subarrays grows as O(n²). For n = 1000, there are 500,500 subarrays.

c

int arr[1000]; /* 500,500 subarrays - may exhaust memory if stored */

Solution: Print subarrays incrementally instead of storing all.

5. Memory Leaks

Storing subarrays with malloc requires freeing each one.

c

for (int i = 0; i < count; i++) { free(collection->items[i].elements); } free(collection->items); free(collection);

Solution: Always free dynamically allocated memory.

6. Buffer Overflow

Using fixed-size buffers for subarrays may overflow for large arrays.

c

int current[100]; // BUG if n > 100

Solution: Allocate dynamically or use larger buffers.

7. Off-by-One Errors

Incorrect loop bounds produce missing or extra subarrays.

c

for (int j = i; j < n; j++) // Correct: j < n for (int j = i; j <= n; j++) // BUG: j <= n accesses out of bounds

Solution: Use j < n for inclusive ending index.

8. Integer Overflow in Sum

Summing large subarrays may overflow.

c

int sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; // May overflow for large values }

Solution: Use long long for sum calculations.

9. Recursion Depth

Recursive generation may cause stack overflow for large arrays.

Solution: Use iterative approach for large arrays.

10. Memory Considerations

• Number of subarrays = n × (n + 1) / 2.
• Each subarray of average length n/3 uses O(n) memory.
• Total memory for storing all subarrays: O(n³).
• For large n, print subarrays instead of storing.

---

Summary & Best Practices

Generating all subarrays is a fundamental operation with applications in algorithm design, data analysis, and interview preparation. Iterative approaches are simple; recursive approaches are elegant but less efficient.

Key Takeaways

• Subarrays are contiguous portions of an array.
• Number of subarrays = n × (n + 1) / 2.
• Iterative approach: O(n³) or O(n²) time.
• Recursive approach: O(n³) time, O(n) stack space.
• Subarrays must be distinct by position, not value.
• Store only when needed; print incrementally for large arrays.

Best Practices

1. Use iterative approach for simplicity and efficiency.
2. Use recursion only for educational purposes or specific requirements.
3. Avoid storing all subarrays for large arrays (memory).
4. Free dynamically allocated memory for subarrays.
5. Handle empty arrays and single-element arrays.
6. Use long long for sum calculations to prevent overflow.
7. Use size_t for array sizes.
8. Print incrementally for large arrays.
9. Validate array size before generation.
10. Test with edge cases: empty, single element, duplicates, negatives.

By mastering subarray generation, you’ll build a foundation for solving more complex array and range-based problems.