[go: up one dir, main page]
Scribd
Upload
14 views2 pages

Assignment 15 Subset Sum Problem

The document presents an assignment to implement the Subset Sum Problem using two approaches: dynamic programming and backtracking. It includes C code for both methods, demonstrating how to check for subsets that sum to a specified value. The dynamic programming approach initializes a table to track possible sums, while the backtracking method recursively explores subsets to find valid combinations.

Uploaded by

roysayanccp05
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
14 views2 pages

Assignment 15 Subset Sum Problem

The document presents an assignment to implement the Subset Sum Problem using two approaches: dynamic programming and backtracking. It includes C code for both methods, demonstrating how to check for subsets that sum to a specified value. The dynamic programming approach initializes a table to track possible sums, while the backtracking method recursively explores subsets to find valid combinations.

Uploaded by

roysayanccp05
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Assignment – 15

To implement and solve the Subset Sum Problem using (a) dynamic programming and (b)
backtracking approaches.

Code:

(a) Using Dynamic Programming


#include <stdio.h>
#include <stdbool.h>

// Function to check if there's a subset with given sum


bool isSubsetSum(int set[], int n, int sum) {
bool dp[n+1][sum+1];

// Initialize the dp table


for (int i = 0; i <= n; i++)
dp[i][0] = true; // Sum 0 is always possible with empty subset

for (int j = 1; j <= sum; j++)


dp[0][j] = false; // Non-zero sum is not possible with 0 elements

// Fill the subset table


for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (set[i-1] > j)
dp[i][j] = dp[i-1][j]; // Exclude current element
else
dp[i][j] = dp[i-1][j] || dp[i-1][j - set[i-1]]; // Include or exclude
}
}

return dp[n][sum];
}

// Main function to test the above code


int main() {
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);

if (isSubsetSum(set, n, sum))
printf("Found a subset with given sum.\n");
else
printf("No subset with given sum.\n");

return 0;
}

Output:
Found a subset with given sum.
(b) Using Backtracking Approach

#include <stdio.h>
#define SIZE 7
void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
printf("%d ", subSet[i]);
}
printf("\n");
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
//print the subset
displaySubset(subSet, subSize);
//for other subsets
if (subSize != 0)
subsetSum(set,subSet,n,subSize-2,total-set[nodeCount],nodeCount+1,sum);
return;
}else {
//find node along breadth
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//do for next node in depth
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);
}
}
}
void findSubset(int set[], int size, int sum) {
//create subset array to pass parameter of subsetSum
int subSet[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
}
int main() {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = SIZE;
findSubset(weights, size, 35);
return 0;
}
Output:
1 9 7 18
1 9 5 20
5 18 12

You might also like