Sometimes, while working with Python lists, we can have problem in which we need to extract pairs which have sum equal to K. This kind of problem is common and can have application in domains such as web development and day-day programming. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [1, 9, 5, 5, 7] K = 10 Output : [(1, 9), (5, 5)] Input : test_list = [1, 9, 7, 8, 3] K = 12 Output : [(9, 3)]
Method #1 : Using list comprehension + sum() The combination of above functions can be used to solve this problem. In this, we perform the task of finding summation equal to K using sum() and list comprehension is used to logic and pair building.
Python3
# Python3 code to demonstrate working of # Construct Sum pairs equal to K# Using list comprehension + sum()# initializing listtest_list = [3, 4, 0, 5, 2]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 7# Construct Sum pairs equal to K# Using list comprehension + sum()res = [(test_list[idx], test_list[j]) for idx in range(len(test_list)) for j in range(idx + 1, len(test_list)) if sum((test_list[idx], test_list[j])) == K]# printing result print("The paired tuples equal to K : " + str(res)) |
The original list is : [3, 4, 0, 5, 2] The paired tuples equal to K : [(3, 4), (5, 2)]
Time Complexity: O(n) where n is the number of elements in the list “test_list”. list comprehension + sum() performs n number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #2: Using combinations() + sum() The combination of above functions can be used to solve this problem. In this combination() is used to form pairs equal to K.
Python3
# Python3 code to demonstrate working of # Construct Sum pairs equal to K# Using combinations() + sum()from itertools import combinations# initializing listtest_list = [3, 4, 0, 5, 2]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 7# Construct Sum pairs equal to K# Using combinations() + sum()res = [ele for ele in combinations(test_list, 2) if sum(ele) == K]# printing result print("The paired tuples equal to K : " + str(res)) |
The original list is : [3, 4, 0, 5, 2] The paired tuples equal to K : [(3, 4), (5, 2)]
Method #3: Using dictionary
Python3
# Define a function named "find_pairs" that takes two arguments:# - test_list: a list of integers# - K: an integer representing the target sum of pairsdef find_pairs(test_list, K): # Create an empty list to hold the resulting pairs result = [] # Create an empty dictionary to keep track of seen numbers seen = {} # Iterate over each number in the input list for num in test_list: # Calculate the difference between the target sum and the current number diff = K - num # Check if the difference is already in the seen dictionary if diff in seen: # If so, add a tuple of the current number and the difference to the result list result.append((diff, num)) # Add the current number to the seen dictionary seen[num] = True # Return the resulting pairs list return result# Create a test list of integerstest_list = [1, 9, 5, 5, 7]# Define the target sum of pairsK = 10# Call the "find_pairs" function with the test list and target sum as arguments,# and print the resulting pairs listprint(find_pairs(test_list, K)) |
[(1, 9), (5, 5)]
Time complexity: O(n)
Auxiliary space: O(min(n, K)).
Method #4: Using recursion:
- Define a function named “find_pairs” that takes two arguments: test_list and K
- Initialize an empty list named “result” to hold the resulting pairs
- Check if the length of the test list is less than 2. If so, return the empty result list
- Take the first element of the test list and assign it to a variable named “first_num”
- Create a new list named “rest_list” by slicing the original list from the second element to the end
Iterate over each element in the rest_list and check if the difference between K and the first_num is equal to the current element - If it is, append a tuple of the first_num and the current element to the result list
- Recursively call the “find_pairs” function with the rest_list as the new test list
- Add the resulting pairs list from the recursive call to the result list
- Return the resulting pairs list
Python3
def find_pairs(test_list, K): # Initialize an empty list to hold the resulting pairs result = [] # Base case: if the length of the test list is less than 2, return the empty result list if len(test_list) < 2: return result # Recursive case: # - take the first element of the test list # - find all elements in the rest of the list that add up to K minus the first element # - add each pair of elements to the result list # - recursively call the function with the rest of the list as the new test list else: first_num = test_list[0] rest_list = test_list[1:] for num in rest_list: if num == K - first_num: result.append((first_num, num)) result += find_pairs(rest_list, K) # Return the resulting pairs list return result # Create a test list of integerstest_list = [1, 9, 5, 5, 7]# printing original listprint("The original list is : " + str(test_list))K = 10res = find_pairs(test_list, K)# printing resultprint("The paired tuples equal to K : " + str(res))#This code is contributed by Jyothi Pinjala. |
The original list is : [1, 9, 5, 5, 7] The paired tuples equal to K : [(1, 9), (5, 5)]
Time complexity: O(n^2), where n is the length of the input test_list. This is because in the worst case, every element in the list will be compared with every other element in the list.
Auxiliary space: O(n), since the result list and seen dictionary will each contain at most n elements.
Method #5: Using nested loop
- Initialize a list to store the pairs of elements that sum to K.
- Loop through the list and select the first element.
- Loop through the remaining elements in the list and compare the sum of the first element and each remaining element with K.
- If the sum equals K, add the pair of elements to the list of pairs.
- Continue looping through the remaining elements in the list, comparing their sum with the first element, until all pairs have been checked.
- Repeat steps 2-5 for all elements in the list.
- Return the list of pairs.
Python3
# Python3 code to demonstrate working of# Construct Sum pairs equal to K# Using nested loop# initializing listtest_list = [3, 4, 0, 5, 2]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 7# Construct Sum pairs equal to K# Using nested looppairs = []for i in range(len(test_list)): for j in range(i+1, len(test_list)): if test_list[i] + test_list[j] == K: pairs.append((test_list[i], test_list[j]))# printing resultprint("The paired tuples equal to K : " + str(pairs)) |
The original list is : [3, 4, 0, 5, 2] The paired tuples equal to K : [(3, 4), (5, 2)]
Time complexity: O(n^2), where n is the length of the list, because we are using a nested loop to iterate through the list.
Auxiliary space: O(k), where k is the number of pairs that sum to K, because we are storing each pair in a list.
