Scribd
Upload
9 views2 pages

Subset Problem

The document contains a C program that solves the subset sum problem, where the user inputs a set of elements and a target sum. The program checks for subsets of the input elements that add up to the specified sum and prints them. If no valid subsets are found, it outputs 'No solution'.

Uploaded by

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

Subset Problem

The document contains a C program that solves the subset sum problem, where the user inputs a set of elements and a target sum. The program checks for subsets of the input elements that add up to the specified sum and prints them. If no valid subsets are found, it outputs 'No solution'.

Uploaded by

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

Subset problem

#include <stdio.h>

void subset(int cs, int k, int r);

int x[10], w[10], d, count = 0;

void main() {

int i, n, sum = 0;

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

scanf("%d", &n);

printf("\nEnter the elements in ascending order:\n");

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

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

printf("\nEnter the sum: ");

scanf("%d", &d);

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

sum = sum + w[i];

if (sum < d) {

printf("No solution\n");

return;

subset(0, 0, sum);

if (count == 0) {

printf("No solution\n");

void subset(int cs, int k, int r) {

int i;

x[k] = 1;
if (cs + w[k] == d) {

printf("\nSubset %d: ", ++count);

for (i = 0; i <= k; i++) {

if (x[i] == 1) {

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

printf("\n");

else if (cs + w[k] + w[k + 1] <= d) {

subset(cs + w[k], k + 1, r - w[k]);

if ((cs + r - w[k] >= d) && (cs + w[k] <= d)) {

x[k] = 0;

subset(cs, k + 1, r - w[k]);

You might also like