Python | Sectional subset sum in list

Some of the classical problems in the programming domain come from different categories and one among them is finding the sum of subsets. This particular problem is also common when we need to accumulate the sum and store consecutive group summations. Let’s try different approaches to this problem in Python language. 

Method #1: Using list comprehension + sum()

The list comprehension can be used to perform this particular task to filter out successive groups and the sum function can be used to get the summation of the filtered solution. 

The original list : [4, 7, 8, 10, 12, 15, 13, 17, 14]
The grouped summation list is : [19, 37, 44]

Time complexity: O(n), where n is the length of the input list. This is because the code iterates over the input list once, creating subsets of size 3 at each step.
Auxiliary space: O(m), where m is the number of subsets of size 3 in the input list. This is because the code creates a new list of size m to store the summed values of each subset.

Method #2 : Using sum() + itertools.islice() 

The task of slicing the list into chunks is done by islice method here and the conventional task of getting the summation is done by the sum function as the above method.

The original list : [4, 7, 8, 10, 12, 15, 13, 17, 14]
The grouped summation list is : [19, 37, 44]

Method #3 : Using itertools + sum()

To use the islice function from the itertools module, the built-in sum function, and a list comprehension to group the elements of the list into chunks of the desired size and sum each chunk, you can use the following approach:

[19, 37, 44]
[3, 7, 11, 15, 9]
[10, 26, 9]

Time complexity: O(n)
Auxiliary space: O(n)

Method 4: Using a loop to iterate over the list in chunks of the desired size and summing each chunk.

This function works similarly to the original one, but instead of using a list comprehension and itertools.islice to group the elements of the list into chunks, it uses a loop to iterate over the list in chunks of the desired size (specified by the chunk_size parameter) and sum each chunk using the built-in sum() function. The sums are stored in a list and returned at the end.

Algorithm:

1. Define the function sectional_subset_sum(lst, chunk_size), which takes two arguments: lst, the list of integers to be grouped into chunks, and chunk_size, the desired size of each chunk.
2. Initialize an empty list called result to store the sums of each chunk.
3. Use a for loop to iterate over the indices of lst in steps of chunk_size. This will create a sequence of starting indices for each chunk.
4. For each starting index i, create a slice of lst that starts at i and ends at i + chunk_size. This will extract a chunk of lst with chunk_size elements.
5. Use the built-in sum() function to sum the elements of the current chunk.
6. Append the sum of the current chunk to the result list using the append() method.
7. After all, chunks have been processed, return the result list containing the sums of each chunk.

[19, 37, 44]
[3, 7, 11, 15, 9]
[10, 26, 9]

Time complexity: O(n), where n is the length of the input list, since it it iterates over the list once. 
Auxiliary space: O(n) since the function creates a list to store the sums.

Method #5: Using numpy.array_split() and numpy.sum()

Approach:

1. Import the NumPy library.
2. Convert the given list into a NumPy array using the np.array() function.
3. Use the np.array_split() function to split the array into chunks of the desired size.
4. Use the np.sum() function to calculate the sum of each chunk.
5. Return the list of sums.

OUTPUT:

[19, 37, 44]
[6, 9, 13, 17]
[15, 30]

The time complexity of this program is O(n), where n is the length of the input list. The auxiliary space complexity is O(n), since the program creates an array of size n and a list of size n.

Method #6: Using a generator function and sum()

1. Define a generator function sectional_subset_sum that takes two arguments: lst, the input list, and n, the size of each section.
2. Use a for loop to iterate over the indices of the list, with a step size of n.
3. In each iteration, yield the sum of the sublist from the current index to the next n indices.
4. Convert the generator to a list using the list() function and store the result in res.
5. Print the result.

The grouped summation list is : [19, 37, 44]

Time complexity: O(n), where n is the length of the list.
Auxiliary space: O(1)