Python-এ একটি লিস্ট থেকে নির্দিষ্ট যোগফল (s) 가진 সকল সাবসেট খুঁজে বের করতে itertools.combinations ব্যবহার করা হয়। এটি সমস্ত সম্ভাব্য কবিনেশন তৈরি করে এবং যোগফল মিলিয়ে ফিল্টার করে।
উদাহরণ কোড
from itertools import combinations
def sub_set_sum(size, my_array, target_sum):
for i in range(size + 1):
for my_sub_set in combinations(my_array, i):
if sum(my_sub_set) == target_sum:
print(list(my_sub_set))
my_size = 6
my_list = [21, 32, 56, 78, 45, 99, 0]
print("The list is:")
print(my_list)
subset_sum = 53
print("The result is:")
sub_set_sum(my_size, my_list, subset_sum)আউটপুট
The list is: [21, 32, 56, 78, 45, 99, 0] The result is: [21, 32] [21, 32, 0]
ব্যাখ্যা
combinations(my_array, i)—iদৈর্ঘ্যের সকল কবিনেশন তৈরি করে।- লুপ
range(size + 1)— ০ থেকেsizeদৈর্ঘ্যের সব কবিনেশন চেক করে। sum(my_sub_set) == target_sum— যোগফল মিললে প্রিন্ট করে।- উদাহরণে
0থাকায়[21, 32]এবং[21, 32, 0]দুটোই যোগফল ৫৩ দেয়।
নোট
বড় লিস্টের জন্য এই পদ্ধতি ধীর হতে পারে (exponential complexity)। সেক্ষেত্রে ডাইনামিক প্রোগ্রামিং বা ব্যাকট্র্যাকিং ব্যবহার করা ভালো।
