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?

CodePudding user response：

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
}

CodePudding user response：

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  )
                result.add(list.subList(j, Math.min(j   counter, arr.length)));

            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], [1, 1, 1, 1], [1, 1, 1], [1, 1], [1]]