Backtracking là một kỹ thuật để giải quyết các vấn đề lập trình động. Nó hoạt động bằng cách đi từng bước và từ chối những con đường không dẫn đến giải pháp và theo dõi trở lại (di chuyển trở lại) về vị trí cũ.
Trong bài toán tổng của tập hợp con, chúng ta phải tìm tập hợp con của một tập hợp sao cho phần tử của tập hợp con này tổng thành một số cho trước K. Tất cả các phần tử của tập hợp là dương và duy nhất (không có phần tử nào trùng lặp ).
Đối với điều này, chúng tôi sẽ tạo các tập hợp con và kiểm tra xem tổng của chúng có bằng số k đã cho hay không. Hãy xem một chương trình để tạo ra một giải pháp.
Ví dụ
#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;
} Đầu ra
The set is 5 6 12 54 2 20 15 5 6 12 2 5 20 Total Nodes generated 127