ব্যাকট্র্যাকিং (Backtracking) হল ডাইনামিক প্রোগ্রামিং সমস্যা সমাধানের একটি টেকনিক। এটি ধাপে ধাপে কাজ করে এবং সেই পথগুলো রিজেক্ট করে যা কোনো সমাধানের দিকে নিয়ে যায় না এবং পिछনে ফিরে যায় (trackback/moves back) আগের পজিশনে।
সাবসেট সম প্রোব্লেম (Subset Sum Problem)-এ, আমাদের একটি সেটের সাবসেট (subset) এমনভাবে খুঁজে বের করতে হয় যাতে এই সাবসেটের এলিমেন্টগুলোর যোগফল (sum) একটি দেয়া সংখ্যা K-র সমান হয়। সেটের সব এলিমেন্ট পজিটিভ এবং ইউনিক (unique) (কোনো ডুপ্লিকেট এলিমেন্ট নেই)।
এজন্য, আমরা সাবসেটগুলো তৈরি করব এবং চেক করব তাদের যোগফল দেওয়া সংখ্যা k-র সমান কিনা। সমাধান বুঝতে প্রোগ্রামটি দেখুন।
উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printValues(int A[], int size) {
for (int i = 0; i < size; i++) {
printf("%*d", 5, A[i]);
}
printf("\n");
}
void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const target_sum) {
total_nodes++;
if (target_sum == sum) {
printValues(t, t_size);
subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
return;
} else {
for (int i = ite; i < s_size; i++) {
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
void generateSubsets(int s[], int size, int target_sum) {
int* tuplet_vector = (int*)malloc(size * sizeof(int));
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);
}
int main() {
int set[] = {5, 6, 12, 54, 2, 20, 15};
int size = sizeof(set) / sizeof(set[0]);
printf("The set is ");
printValues(set, size);
generateSubsets(set, size, 25);
printf("Total Nodes generated %d\n", total_nodes);
return 0;
}
আউটপুট
The set is 5 6 12 54 2 20 15 5 6 12 2 5 20 Total Nodes generated 127
ব্যাখ্যা: সেট {5, 6, 12, 54, 2, 20, 15} থেকে টার্গেট সম 25 পাওয়ার জন্য দুটি সাবসেট পাওয়া গেলো: {5, 6, 12, 2} (যোগফল ২৫) এবং {5, 20} (যোগফল ২৫)। টোটাল ১২৭টি নোড জেনারেট হয়েছে ব্যাকট্র্যাকিং প্রক্রিয়ায়।
