Given a list, our task is to write a Python program to extract all K length sublists with lead to given summation.
Input : test_list = [6, 3, 12, 7, 4, 11], N = 21, K = 4
Output : [(6, 6, 6, 3), (6, 6, 3, 6), (6, 3, 6, 6), (6, 7, 4, 4), (6, 4, 7, 4), (6, 4, 4, 7), (3, 6, 6, 6), (3, 3, 3, 12), (3, 3, 12, 3), (3, 3, 4, 11), (3, 3, 11, 4), (3, 12, 3, 3), (3, 7, 7, 4), (3, 7, 4, 7), (3, 4, 3, 11), (3, 4, 7, 7), (3, 4, 11, 3), (3, 11, 3, 4), (3, 11, 4, 3), (12, 3, 3, 3), (7, 6, 4, 4), (7, 3, 7, 4), (7, 3, 4, 7), (7, 7, 3, 4), (7, 7, 4, 3), (7, 4, 6, 4), (7, 4, 3, 7), (7, 4, 7, 3), (7, 4, 4, 6), (4, 6, 7, 4), (4, 6, 4, 7), (4, 3, 3, 11), (4, 3, 7, 7), (4, 3, 11, 3), (4, 7, 6, 4), (4, 7, 3, 7), (4, 7, 7, 3), (4, 7, 4, 6), (4, 4, 6, 7), (4, 4, 7, 6), (4, 11, 3, 3), (11, 3, 3, 4), (11, 3, 4, 3), (11, 4, 3, 3)]
Explanation : All groups of length 4 and sum 21 are printed.
Input : test_list = [6, 3, 12, 7, 4, 11], N = 210, K = 4
Output : []
Explanation : Since no 4 size group sum equals 210, no group is printed as result.
Method : Using sum() + product() + loop
In this all possible sublists of length K are computed using product(), sum() is used to compare the sublist’s sum with the required summation.
Python3
# Python3 code to demonstrate working of# K length groups with given summation# Using sum + product()from itertools import product# initializing listtest_list = [6, 3, 12, 7, 4, 11] # printing original listprint("The original list is : " + str(test_list))# initializing Summation N = 21# initializing size K = 4# Looping for each product and comparing with required summationres = []for sub in product(test_list, repeat = K): if sum(sub) == N: res.append(sub) # printing resultprint("The sublists with of given size and sum : " + str(res)) |
Output:
The original list is : [6, 3, 12, 7, 4, 11]
The sublists with of given size and sum : [(6, 6, 6, 3), (6, 6, 3, 6), (6, 3, 6, 6), (6, 7, 4, 4), (6, 4, 7, 4), (6, 4, 4, 7), (3, 6, 6, 6), (3, 3, 3, 12), (3, 3, 12, 3), (3, 3, 4, 11), (3, 3, 11, 4), (3, 12, 3, 3), (3, 7, 7, 4), (3, 7, 4, 7), (3, 4, 3, 11), (3, 4, 7, 7), (3, 4, 11, 3), (3, 11, 3, 4), (3, 11, 4, 3), (12, 3, 3, 3), (7, 6, 4, 4), (7, 3, 7, 4), (7, 3, 4, 7), (7, 7, 3, 4), (7, 7, 4, 3), (7, 4, 6, 4), (7, 4, 3, 7), (7, 4, 7, 3), (7, 4, 4, 6), (4, 6, 7, 4), (4, 6, 4, 7), (4, 3, 3, 11), (4, 3, 7, 7), (4, 3, 11, 3), (4, 7, 6, 4), (4, 7, 3, 7), (4, 7, 7, 3), (4, 7, 4, 6), (4, 4, 6, 7), (4, 4, 7, 6), (4, 11, 3, 3), (11, 3, 3, 4), (11, 3, 4, 3), (11, 4, 3, 3)]
Time Complexity: O(n*n)
Auxiliary Space: O(n)
Approach#2: Using recursion: The approach uses backtracking to generate all possible groups of length K with sum N. It starts with an empty group and recursively tries to add numbers from the given list to form a group. If the group becomes of length K and its sum is N, it is added to the list of groups.
- Define a backtrack function that takes curr_group, remaining_sum, and remaining_len as parameters.
- Check if remaining_sum is equal to 0 and remaining_len is equal to 0. If yes, return the current group as a list of list.
- Check if remaining_sum is less than 0 or remaining_len is less than 0. If yes, return an empty list.
- Initialize an empty list of groups to store all possible groups.
- Loop through the given list test_list using the enumerate() function.
- Add the current number to the current group to form a new group and reduce the remaining_sum and remaining_len accordingly.
- Recursively call the backtrack function with the new group, new_sum, new_len, and remaining_list.
- Append the returned groups to the groups list.
- Return the final groups list.
Python3
# Python program for the above approach# Function to get the K length groupsdef get_k_length_groups(test_list, N, K): # Function to recursively find the states def backtrack(curr_group, remaining_sum, remaining_len): if remaining_sum == 0 and remaining_len == 0: return [curr_group] if remaining_sum < 0 or remaining_len < 0: return [] groups = [] # Update the group and call recursively for i, num in enumerate(test_list): new_group = curr_group + [num] new_sum = remaining_sum - num new_len = remaining_len - 1 remaining_list = test_list[i:] groups += backtrack(new_group, new_sum, new_len) # Return the groups return groups # Backtrack the current state groups = backtrack([], N, K) # Return the resultant groups return groups# Driver Codetest_list = [6, 3, 12, 7, 4, 11]N = 21K = 4print(get_k_length_groups(test_list, N, K)) |
[[6, 6, 6, 3], [6, 6, 3, 6], [6, 3, 6, 6], [6, 7, 4, 4], [6, 4, 7, 4], [6, 4, 4, 7], [3, 6, 6, 6], [3, 3, 3, 12], [3, 3, 12, 3], [3, 3, 4, 11], [3, 3, 11, 4], [3, 12, 3, 3], [3, 7, 7, 4], [3, 7, 4, 7], [3, 4, 3, 11], [3, 4, 7, 7], [3, 4, 11, 3], [3, 11, 3, 4], [3, 11, 4, 3], [12, 3, 3, 3], [7, 6, 4, 4], [7, 3, 7, 4], [7, 3, 4, 7], [7, 7, 3, 4], [7, 7, 4, 3], [7, 4, 6, 4], [7, 4, 3, 7], [7, 4, 7, 3], [7, 4, 4, 6], [4, 6, 7, 4], [4, 6, 4, 7], [4, 3, 3, 11], [4, 3, 7, 7], [4, 3, 11, 3], [4, 7, 6, 4], [4, 7, 3, 7], [4, 7, 7, 3], [4, 7, 4, 6], [4, 4, 6, 7], [4, 4, 7, 6], [4, 11, 3, 3], [11, 3, 3, 4], [11, 3, 4, 3], [11, 4, 3, 3]]
Time Complexity: O(N^K), because we are generating all possible groups of length K with sum N, and each number in the list, can either be included or excluded in a group.
Space Complexity: O(K) because we are using the curr_group list to store the current group, and its length is at most K. Additionally, the recursion depth can go up to K, so the space complexity is O(K).
