Advertisement
warrior07

minimum subset sum into equal subsets

Aug 26th, 2020
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.64 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ans=INT_MAX;
  4. void helper1(int ar[],int n1,int n,int i,int sum,int tmpsum,int ct)
  5. {
  6. if(ct==n1)
  7. {
  8. int diff1=sum-tmpsum;
  9. int diff=abs(diff1-tmpsum);
  10. if(diff<ans)
  11. ans=diff;
  12. return;
  13. }
  14. if(i==n)
  15. return;
  16. helper1(ar,n1,n,i+1,sum,tmpsum+ar[i],ct+1);
  17. helper1(ar,n1,n,i+1,sum,tmpsum,ct);
  18. }
  19. int helper(int ar[],int n)
  20. {
  21. int sum=0;
  22. for(int i=0;i<n;i++)
  23. sum+=ar[i];
  24. ans=INT_MAX;
  25.  
  26. int n1=n/2;
  27. int tmpsum=0;
  28. int i=0;
  29. int ct=0;
  30. helper1(ar,n1,n,i,sum,tmpsum,ct);
  31. return ans;
  32. }
  33. int main()
  34. {
  35. int n=5;
  36. int ar[]={1,4,9,12,17};
  37. cout<<helper(ar,n)<<endl;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement