Thanks guys. I found a solution from "Perfect subset Sum" problem and then made a few changes in it. Here's the code.
#include <bits/stdc++.h> using namespace std; bool dp[100][100]; int sizeOfJoints = -1; void display(const vector<int>& v) { if (sizeOfJoints == -1) { sizeOfJoints = v.size() - 1; } else if (v.size()< sizeOfJoints) { sizeOfJoints = v.size() - 1; } } // A recursive function to print all subsets with the // help of dp[][]. Vector p[] stores current subset. void printSubsetsRec(int arr[], int i, int sum, vector<int>& p) { // If sum becomes 0 if (sum == 0) { display(p); return; } if(i<=0 || sum<0) return; // If given sum can be achieved after ignoring // current element. if (dp[i-1][sum]) { // Create a new vector to store path //vector<int> b = p; printSubsetsRec(arr, i-1, sum, p); } // If given sum can be achieved after considering // current element. if (sum >= arr[i-1] && dp[i-1][sum-arr[i-1]]) { p.push_back(arr[i-1]); printSubsetsRec(arr, i-1, sum-arr[i-1], p); p.pop_back(); } } // all subsets of arr[0..n-1] with sum 0. void printAllSubsets(int arr[], int n, int sum) { if (n == 0 || sum < 0) return; // If sum is 0, then answer is true for (int i = 0; i <= n; i++) dp[i][0] = true; // If sum is not 0 and set is empty, then answer is false for (int i = 1; i <= sum; i++) dp[0][i] = false; // Fill the subset table in botton up manner for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { if(j<arr[i-1]) dp[i][j] = dp[i-1][j]; if (j >= arr[i-1]) dp[i][j] = dp[i-1][j] || dp[i - 1][j-arr[i-1]]; } } if (dp[n][sum] == false) { return; } // Now recursively traverse dp[][] to find all // paths from dp[n-1][sum] vector<int> p; printSubsetsRec(arr, n, sum, p); } // Driver code int main() { int input[2000]; int inputIndex = 0; int i = 0; int distance = 0; cout<< "Enter Input: " <<endl; cin>> distance; while(true) { int temp1 = 0; int temp2 = 0; cin>> temp1; cin>> temp2; if (temp1 == 0 && temp2 == 0) { break; } for (i = 0; i < temp2; i++) input[inputIndex++] = temp1; } cout<< "Processing output. Please wait: " <<endl; printAllSubsets(input, inputIndex, distance); if(sizeOfJoints != -1) cout<<sizeOfJoints; else cout<<"No Solution Possible"; return 0; }
