बैट्रैकिंग डायनामिक प्रोग्रामिंग समस्याओं को हल करने की एक तकनीक है। यह चरण दर चरण काम करता है और उन पथों को अस्वीकार करता है जो समाधान की ओर नहीं ले जाते और पिछली स्थिति पर वापस आ जाता है (ट्रैकबैक)।
सबसेट सम समस्या में, हमें एक सेट का सबसेट इस तरह ढूंढना होता है कि इस सबसेट के तत्व दिए गए नंबर K तक जुड़ जाएं। सेट के सभी तत्व सकारात्मक और अद्वितीय हैं (कोई डुप्लिकेट तत्व मौजूद नहीं हैं)।
इसके लिए, हम सबसेट बनाएंगे और जांचेंगे कि क्या उनका योग दी गई संख्या k के बराबर है। आइए एक समाधान बनाने के लिए एक प्रोग्राम देखें।
उदाहरण
#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
