4. Write a program to implement the backtracking algorithm for the sum of subsets problem || DAA

#include <stdio.h> 

#include <stdbool.h> 

void printSubset(int subset[], int size) { 

printf("Subset: { "); 

for (int i = 0; i < size; i++) { 

printf("%d ", subset[i]); 

} 

printf("}\n"); 

} 

void sumOfSubsetsUtil(int weights[], int targetSum, int n, int subset[], int subsetSize, int sum, 

int index) { 

if (sum == targetSum) { printSubset(subset, subsetSize); return; 

} 

for (int i = index; i < n; i++) { 

if (sum + weights[i] <= targetSum) { 

subset[subsetSize] = weights[i]; 

sumOfSubsetsUtil(weights,   targetSum,   n,   subset,   subsetSize   +   1,   sum   + 

weights[i], i + 1); 

} 

} 

} 

void sumOfSubsets(int weights[], int targetSum, int n) { 

int subset[n]; 

sumOfSubsetsUtil(weights, targetSum, n, subset, 0, 0, 0); 

} 

int main() {

    int n, targetSum; 

printf("Enter the number of elements: "); 

scanf("%d", &n); 

int weights[n]; 

printf("Enter the elements: "); 

for (int i = 0; i < n; i++) { 

scanf("%d", &weights[i]); 

} 

printf("Enter the target sum: "); 

scanf("%d", &targetSum); 

sumOfSubsets(weights, targetSum, n); 

return 0; 

}