lets solve the problem by finding 4 sets has same sum and the total sum is divisible by 4
there is a nice recurrence you can find when looking to the problem as find One subset {not four} has sum k and mark the elements that you have chosen to build this subset ,
bool Canmake(int index, int sum) { if(sum==0) return 1; else if(sum<0|| index == m ) return 0; else { if(sum>=sticks[index]&& !visited [index]) { visited [index]=1; // mark the elements you want to choose to build the subset if(Canmake(index +1 , sum - sticks[index])) return 1; visited [index]=0; } if(Canmake(index +1 , sum) ) return 1; } return 0; }
so if we have 8 elements {1,2,1,2,1,2,1,2} and we want to build a subset has sum==(k)== 3 ,
at the end we will have visited {1, 1 ,0,0,0,0,0,0 } ,
you Can now add another parameter (number of subsets ) to solve the big problem
and change the( return 1 ) to return Canmake(0,numberofsets-1,k), which means that we have One subset has sum == k so lets find the remaining 3 subsets
#include <stdio.h> #include <math.h> #include <stdlib.h> #include <cstring> #include<iostream> using namespace std; int sticks[25]; bool visited [25]; int k; int m,l; int sum; bool Canmake(int index, int numberofsets, int sum) { if(numberofsets==0) return 1; else if(sum==0) //we have found one subset so lets find the remaking return Canmake(0,numberofsets-1,k); else if(sum<0|| index == m || numberofsets <0) return 0; else { if(sum>=sticks[index]&& !visited [index]) { visited [index]=1; if(Canmake(index +1 , numberofsets , sum - sticks[index])) return 1; visited [index]=0; } if(Canmake(index +1 , numberofsets , sum) ) return 1; } return 0; } int main() { int n; scanf("%d",&n); while(n--) { sum=0; scanf("%d",&m); for(int i=0; i<m; i++) { scanf("%d",&l); sum+=l; sticks[i]=l; } if(sum%4!=0) printf("no\n"); else { k=sum/4; memset(visited ,0,sizeof visited ); if(Canmake(0,4,k)) printf("yes\n"); else printf("no\n"); } } return 0; }
there is another Dp solution for that problem 🙂