बैकट्रैकिंग गतिशील प्रोग्रामिंग समस्याओं को हल करने की एक तकनीक है। यह कदम दर कदम चलकर काम करता है और उन रास्तों को खारिज कर देता है जो समाधान की ओर नहीं ले जाते हैं और पिछली स्थिति में ट्रैकबैक (वापस ले जाते हैं)।
उपसमुच्चय योग समस्या में, हमें एक समुच्चय का उपसमुच्चय इस प्रकार ज्ञात करना है कि इस उपसमुच्चय का अवयव दी गई संख्या 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