Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....
,sn} of n positive
integers whose sum is equal to a given positive integer d.
Here is an optimized C++ program that uses STL libraries to find all subsets of a given set S = {s₁,
s₂, ..., sₙ} that sum to a target value d. The program prints all such subsets using backtracking with
recursion.
📌 Explanation
findSubsets(...) uses recursion to explore all combinations of elements.
It includes or excludes each element to form subsets.
If the current sum equals d, it prints that subset.
The function handles multiple valid subsets.
🖥️ Sample Output
Set: { 3 34 4 12 5 2 }
Target Sum: 9
Subsets with sum 9 are:
{342}
{45}
Here is a detailed tracing of the subset sum program that prints all subsets summing to a given target
d
✅ Input
Set S = {3, 34, 4, 12, 5, 2}
Target sum d = 9
The goal is to print all subsets of S that sum to 9.
🧠 Function Flow Recap
The function is:
void findSubsets(vector<int>& set, int index, int target, vector<int>& current)
It explores:
Including the current element (set[index])
Excluding the current element
Stops if:
o target == 0: prints the subset
o index == set.size() or target < 0: terminates path
🧠 Step-by-Step Tracing (Partial)
Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive
integers whose sum is equal to a given positive integer d.
Let's trace through a few key recursive steps:
▶️ Step 1: Start with index = 0, target = 9
current = {}
element = 3
New target = 9 - 3 = 6
Recursive call with:
current = {3}
index = 1
target = 6
▶️ Step 2: index = 1, target = 6, element = 34
Include 34 → new target = 6 - 34 = -28 ❌ (invalid, backtrack)
Exclude 34 → move to index 2
Now:
current = {3}
index = 2
target = 6
▶️ Step 3: index = 2, target = 6, element = 4
Include 4 → new target = 6 - 4 = 2
current = {3, 4}
Recursive call:
index = 3
target = 2
▶️ Step 4: index = 3, target = 2, element = 12
Include 12 → 2 - 12 = -10 ❌
Exclude 12 → index = 4
Now:
current = {3, 4}
target = 2
index = 4, element = 5
Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive
integers whose sum is equal to a given positive integer d.
▶️ Step 5: index = 4, target = 2, element = 5
Include 5 → 2 - 5 = -3 ❌
Exclude 5 → index = 5
Now:
current = {3, 4}
target = 2
index = 5, element = 2
▶️ Step 6: index = 5, target = 2, element = 2
Include 2 → 2 - 2 = 0 ✅
current = {3, 4, 2} → Valid subset found!
Printed: { 3 4 2 }
Backtrack to index 5, try without 2 — leads to index = 6 (end of array) → return
✅ Second Valid Path (Quick Trace)
Exclude 3 → index = 1
Exclude 34 → index = 2
Include 4 → current = {4}, target = 5
Exclude 12 → index = 4
Include 5 → target = 0
Subset found: {4, 5}
✅ Final Output
Subsets with sum 9 are:
{342}
{45}
#include <iostream>
#include <vector>
using namespace std;
Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive
integers whose sum is equal to a given positive integer d.
// Function to print a subset
void printSubset(const vector<int>& subset) {
cout << "{ ";
for (int num : subset)
cout << num << " ";
cout << "}" << endl;
// Recursive function to find subsets
void findSubsets(vector<int>& set, int index, int target, vector<int>& current) {
if (target == 0) {
printSubset(current);
return;
if (index == set.size() || target < 0)
return;
// Include current element
current.push_back(set[index]);
findSubsets(set, index + 1, target - set[index], current);
// Exclude current element (backtrack)
current.pop_back();
findSubsets(set, index + 1, target, current);
int main() {
vector<int> S = {3, 34, 4, 12, 5, 2};
int d = 9;
cout << "Set: { ";
Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive
integers whose sum is equal to a given positive integer d.
for (int x : S) cout << x << " ";
cout << "}\nTarget Sum: " << d << endl;
cout << "Subsets with sum " << d << " are:\n";
vector<int> current;
findSubsets(S, 0, d, current);
return 0;
