#include<iostream>
using namespace std;
void fun(int arr[],int *p,int index,int low,int high,int sum)
{
	if((sum<0)||(low>high))
	     return;
    if(sum==0)
    {
    	for(int i=0;i<index;i++)
    	{
    		cout<<p[i]<<" ";
    	}
    	cout<<"\n";
    	return;
    }
   p[index]=arr[low];
   fun(arr,p,index+1,low+1,high,sum-arr[low]);
   fun(arr,p,index,low+1,high,sum);
}
int main()
{
	int arr[]={3,1,5,2,4,6,7,8,9,12};
	int n=sizeof(arr)/sizeof(arr[0]);
	int *p=new int[n];
	int sum;
	cout<<"enter the sum.\n";
	cin>>sum;
	fun(arr,p,0,0,n-1,sum);
	return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZvaWQgZnVuKGludCBhcnJbXSxpbnQgKnAsaW50IGluZGV4LGludCBsb3csaW50IGhpZ2gsaW50IHN1bSkKewoJaWYoKHN1bTwwKXx8KGxvdz5oaWdoKSkKCSAgICAgcmV0dXJuOwogICAgaWYoc3VtPT0wKQogICAgewogICAgCWZvcihpbnQgaT0wO2k8aW5kZXg7aSsrKQogICAgCXsKICAgIAkJY291dDw8cFtpXTw8IiAiOwogICAgCX0KICAgIAljb3V0PDwiXG4iOwogICAgCXJldHVybjsKICAgIH0KICAgcFtpbmRleF09YXJyW2xvd107CiAgIGZ1bihhcnIscCxpbmRleCsxLGxvdysxLGhpZ2gsc3VtLWFycltsb3ddKTsKICAgZnVuKGFycixwLGluZGV4LGxvdysxLGhpZ2gsc3VtKTsKfQppbnQgbWFpbigpCnsKCWludCBhcnJbXT17MywxLDUsMiw0LDYsNyw4LDksMTJ9OwoJaW50IG49c2l6ZW9mKGFycikvc2l6ZW9mKGFyclswXSk7CglpbnQgKnA9bmV3IGludFtuXTsKCWludCBzdW07Cgljb3V0PDwiZW50ZXIgdGhlIHN1bS5cbiI7CgljaW4+PnN1bTsKCWZ1bihhcnIscCwwLDAsbi0xLHN1bSk7CglyZXR1cm4gMDsKfQ==