Not able to solve the problem

#1

Hello Sir, I’m generally able to do all those problems that you explain in the video lectures but I really get stuck on the new problems and how to approach them. Currently I’m really stuck on this problem and is unable to find and approach or solution, please give some idea, tip or hint. It would be really helpful.

#2

@hargovind Here is how you should proceed.
Sort the array(non-decreasing).
First remove all the duplicates from array.
Then use recursion and backtracking to solve the problem.

  1. If at any time sub-problem sum == 0 then add that array to the result (vector of vectors).
  2. Else if sum if negative then ignore that sub-problem.
  3. Else insert the present array in that index to the current vector and call the function with sum = sum-ar[index] and index = index, then pop that element from current index (backtrack) and call the function with sum = sum and index = index+1
#3

#include
#include
#include
using namespace std;

vector<vector> v;

void sumItUp(int arr[], int n, int sum, int i, int j){

if(sum==0){
    v[j].push_back(arr[i]);
    j++;
    return;
}
if(i==n){
    return;
}
else if(sum<0){
    return;
}
else{
    v[j].push_back(arr[i]);
    sumItUp(arr, n, sum-arr[i], i+1, j);
    v[j].pop_back();
    i=i+1;
    sumItUp(arr, n, sum, i+1, j);
}

}

int removeDuplicates(int arr[], int n){

if(n==0||n==1){
	return n;
}
int j=0;
for(int i=0; i<=n-1; i++){
	if(arr[i] != arr[i+1]){
		arr[j++] = arr[i];
	}
}

return j;

}

int main() {

int n;
cin >> n;
int arr[n];
for(int i=0; i<n; i++){
	cin >> arr[i];
}
int sum;
cin >> sum;

sort(arr, arr+n);

n = removeDuplicates(arr, n);

sumItUp(arr, n, sum, 0, 0);

for(int i=0; i<v.size(); i++){
    for(int j=0; j<v[i].size(); j++){
        cout << v[i][j] << " ";
    }
    cout << endl;
}

return 0;

}

Sir Please look into the code I have written, I think I am making some mistake in implementation, I slightly got the logic though!

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.