역추적은 동적 프로그래밍 문제를 해결하는 기술입니다. 단계별로 진행하여 솔루션으로 이어지지 않는 경로를 거부하고 이전 위치로 트랙백(뒤로 이동)합니다.
부분집합 합 문제에서 우리는 집합의 부분집합이 주어진 숫자 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