Algorithm to generate all Subarrays from initial Array

Question

How to generate all subarrays from an initial array?

Let's consider an array: [1,1,1,1].

I would like to generate all possible subarrays (in no particular order).

Expected result:

[1], [1], [1], [1], 
[1, 1], [1, 1], [1, 1],
[1, 1, 1], [1, 1, 1],
[1, 1, 1, 1]

My attempt:

List<List<Integer>> list = new ArrayList<>();
generateAllSubArrays(nums, list, 0, 0);

private void generateAllSubArrays(int[] nums, List<List<Integer>> list, int start, int end) {
    if (end == nums.length) {
        List<Integer> l = new ArrayList<>();
        for (int n : nums) {
            l.add(n);
        }
        list.add(l);
    } else if (start > end) {
        generateAllSubArrays(nums, list, 0, end + 1);
    } else {
        List<Integer> l = new ArrayList<>();
        for (int i = start; i < end; i++) {
            l.add(nums[i]);
        }
        list.add(l);
        generateAllSubArrays(nums, list, start + 1, end);
    }
}

I'm getting the following result:

[[], [1], [], [1, 1], [1], [], [1, 1, 1], [1, 1], [1], [], [1, 1, 1, 1]]

Issues:

• Some empty lists [] are present in the result (which is undesired). Unfortunately, I failed to understand why they are here.

• Some of the expected values are absent, making the result incorrect.

What did I do wrong, and what should I do in order to get the correct computation?

I believe what I tried is using some sort of recursion, increasing space and time complexity. What would be the algorithm with the best space and time complexity?

Answer 1

Iterative implementation

Here's the algorithm for generating all non-empty subarrays of the given array iteratively:

• Maintain two nested lists: one for subarrays that are in progress and the resulting list for subarrays that are already built.

• At each iteration step, create a copy of each subarray that is still in progress and add the next element to it. Whilst the original subarray goes into the resulting list intact.

• At the very end of the iteration, add a singleton list containing the next element into the list containing subarrays with we will continue to work, so that on the next iteration step this list would serve as a blueprint for a new subarray and immediately will go into the resulting list.

That's how it can be implemetned:

public static List<List<Integer>> getSubArrays(int[] arr) {
    List<List<Integer>> result = new ArrayList<>();
    List<List<Integer>> inProgress = new ArrayList<>();
    
    for (int next: arr) {
        List<List<Integer>> proceedWith = new ArrayList<>();
        
        for (List<Integer> subArray: inProgress) {
            result.add(subArray); // we are done with this subarray
            
            List<Integer> copy = new ArrayList<>(subArray);
            copy.add(next);
            proceedWith.add(copy); // we should continue working with copy
        }
        
        proceedWith.add(List.of(next)); // to avoid empty subarrays appear in the result
        inProgress = proceedWith;
    }
    
    result.addAll(inProgress);
    
    return result;
}

main()

public static void main(String[] args) {
    int[] arr = {1, 2, 3};
    
    getSubArrays(arr).forEach(System.out::println);
}

Output:

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

Recursive implementation

The main logic remains the same:

• Every subarray serves as a blueprint for another subarray in case if there are some unused elements left.

• Each single-element subarray produces a new branch of subarrays (if there are some unused elements left).

Base case (the condition when recursion should terminate) - there are no elements to explore, i.e. current index is equal to array's length.

Recursive case:

• Create a copy of the subarray received as an argument and add the next element to, original subarray should go into the resulting list.

• Then perform two recursive calls: one with the subarray's copy, another with a single-element subarray (containing the next element).

That's how recursive implementation might look like:

public static List<List<Integer>> getSubArraysRecursively(int[] arr) {
    
    if (arr.length == 0) return Collections.emptyList();
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> subarray = List.of(arr[0]);
    generateSubArrays(result, subarray, arr, 1);
    
    return result;
}

private static void generateSubArrays(List<List<Integer>> result,
                                      List<Integer> subarray,
                                      int[] arr, int i) {
    
    if (i == arr.length) { // base case
        result.add(subarray);
        return;
    }
    
    // recursive case
    result.add(subarray);

    List<Integer> copy = new ArrayList<>(subarray);
    copy.add(arr[i]);
    
    generateSubArrays(result, copy, arr, i + 1); // proceed working with the copy
    
    generateSubArrays(result, List.of(arr[i]), arr, i + 1); // start a new branch of subarrays
}

Answer 2

Using List and stream we can get all SubArrays from an array.

public static void listSubArrays() {
    int[] array = new int[] {1, 2, 3};
    List<List<Integer>> subArrays = new ArrayList<>();
    List<Integer> list =
            Arrays.stream(array).boxed().collect(Collectors.toList());
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++){
            subArrays.add(list.subList(i, j+1));
        }
    }
    subArrays.stream().forEach(System.out::println);
}

Answer 3

List#subList

You can do it with simple nested loops, a counter and some functions e.g. Math#min, List#subList etc. as shown below:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String args[]) {
        int[] arr = { 1, 1, 1, 1 };
        List<Integer> list = Arrays.stream(arr).boxed().toList();
        List<List<Integer>> result = new ArrayList<>();
        int counter = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                List<Integer> sublist = list.subList(j, Math.min(j + counter, arr.length));
                if (sublist.size() == counter)
                    result.add(sublist);
            }
            counter++;
        }

        System.out.println(result);
    }
}

Output:

[[1], [1], [1], [1], [1, 1], [1, 1], [1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1, 1]]