[go: up one dir, main page]

0% found this document useful (0 votes)
47 views3 pages

Subset Sum Problem Using Backtracking Approach.: Code

The document describes an algorithm to solve the subset sum problem using backtracking. It includes C++ code to implement the backtracking algorithm to find subsets of numbers that sum to a target number.

Uploaded by

Hakuna-29 matata
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
0% found this document useful (0 votes)
47 views3 pages

Subset Sum Problem Using Backtracking Approach.: Code

The document describes an algorithm to solve the subset sum problem using backtracking. It includes C++ code to implement the backtracking algorithm to find subsets of numbers that sum to a target number.

Uploaded by

Hakuna-29 matata
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/ 3

Subset Sum problem using backtracking

approach.
By Devansh Kumar (2K19/MC/037)

Code:
#include<bits/stdc++.h>
using namespace std;

bool subsetsum(int *a, int sum, vector<int>&sol, int n, int i){


if (sum == 0){
for (auto it = sol.begin(); it != sol.end(); it++){
cout << *it << " ";
}
cout << endl;
return true;
}
if (i == n){
return false;
}

int freq = 0;
bool inc = false;
for (int j = i; j < n; j++){
if (a[i] == a[j]){
freq++;
}
}
for (int j = freq; j >= 0; j--){
for (int k = 0; k < j; k++){
sol.push_back(a[i]);
}

inc = subsetsum(a, sum - (a[i] * j), sol, n, i + freq) || inc;


for (int k = 0; k < j; k++){
sol.pop_back();
}
}
//int iter=sol.size()-1;

if (inc){
return true;
}

Submitted to: Mr. Dhirendra kumar (CS-262)


return false;
}

int main() {
int n;
cout << "Enter No of Nos. in set: ";
cin >> n;

int a[n];
cout << "\nEnter Nos. one-by one: ";
for (int i = 0; i < n; i++){
cin >> a[i];
}

sort(a, a + n);

vector<int>sol;
int t;
cout << "\nEnter the Target Sum: ";
cin >> t;
cout << "\nThe Subsets are : ";

if (!subsetsum(a, t, sol, n, 0)){


cout << "\nNOT FOUND\n";
}
return 0;
}

Output:

Submitted to: Mr. Dhirendra Kumar sir


Submitted to: Mr. Dhirendra Kumar (CS-262)

You might also like