fork(3) download
copy 
  1. #include <stdio.h> //Code taken and modified from www.geeksforgeeks.org/backttracking-set-4-subset-sum/ 
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. static int total_nodes;
  8. int k,flag=0,x=0,y=0;
  9. vector <int> v;
  10. int c=0;
  11. int a=0,n;
  12. bool checkDuplicates(vector<int> array, int n)
  13. { //To be coded yet..to make disjoint subsets
  14.  
  15. }
  16. // prints subset found
  17. void printSubset(int A[], int size)
  18. {
  19.  
  20.     for(int i = 0; i < size; i++)
  21.     {
  22.          v.push_back(A[i]);
  23.      a++; //Number of elements
  24.      cout<<A[i]<<" ";
  25.      }
  26.     cout<<"\n";
  27.     c++; //Number of subsets
  28.   	if(c==k)
  29.  	{
  30. 	if(!checkDuplicates(v,a)) //If duplicates are not found then set flag = 1
  31. 	{
  32. 		if(a==n)
  33. 		{
  34. 			flag=1;
  35. 		}
  36. 		else 
  37. 		flag=0;
  38. 	 }
  39. 	}
  40.  }
  41.  //	 
  42. // qsort compare function
  43. int comparator(const void *pLhs, const void *pRhs)
  44. {
  45.     int *lhs = (int *)pLhs;
  46.     int *rhs = (int *)pRhs;
  47.  
  48.     return *lhs > *rhs;
  49. }
  50.  
  51. // inputs
  52. // s            - set vector
  53. // t            - tuplet vector
  54. // s_size       - set size
  55. // t_size       - tuplet size so far
  56. // sum          - sum so far
  57. // ite          - nodes  c
  58. // target_sum   - sum to be found
  59. void subset_sum(int s[], int t[],
  60.                 int s_size, int t_size,
  61.                 int sum, int ite,
  62.                 int const target_sum)
  63. {
  64.     total_nodes++;
  65.     if( target_sum == sum )
  66.     {
  67.         // We found sum
  68.         printSubset(t, t_size);
  69.         // constraint check
  70.           if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
  71.         {
  72.             // Exclude previous added item and consider next candidate
  73.             subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
  74.         }
  75.         return;
  76.     }
  77.     else
  78.     {
  79.         // constraint check
  80.         if( ite < s_size && sum + s[ite] <= target_sum )
  81.         {
  82.             // generate nodes along the breadth
  83.             for( int i = ite; i < s_size; i++ )
  84.             {
  85.                 t[t_size] = s[i];
  86.  
  87.                 if( sum + s[i] <= target_sum )
  88.                 {
  89.                     // consider next level node (along depth)
  90.                     subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
  91.                 }
  92.             }
  93.         }
  94.     }
  95.  
  96. 	  //cout<<"INVOKED\n";
  97. }
  98.  
  99. // Wrapper that prints subsets that sum to target_sum
  100. void generateSubsets(int s[], int size, int target_sum)
  101. {
  102.     int *tuplet_vector = (int *)malloc(size * sizeof(int));
  103.  
  104.     int total = 0;
  105.  
  106.     // sort the set
  107.     qsort(s, size, sizeof(int), &comparator);
  108.  
  109.     for( int i = 0; i < size; i++ )
  110.     {
  111.         total += s[i];
  112.     }
  113.  
  114.     if( s[0] <= target_sum && total >= target_sum )
  115.     {
  116.  
  117.         subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
  118.  
  119.     }
  120.     free(tuplet_vector);
  121. }
  122.  
  123. int main()
  124. {
  125. 	int T;
  126. 	int weights[1000];
  127. 	scanf("%d",&T);
  128. 	while(T)
  129. 	{
  130. 		flag=0;
  131. 		long long sum=0;
  132. 		int i=0,w=0;
  133. 		scanf("%d%d",&n,&k);
  134. 		for(int i=0;i<n;i++)
  135. 		{
  136. 		scanf("%d",&weights[i]);
  137. 		sum+=weights[i];
  138. 		if(weights[i]==0)
  139. 		w++;
  140. 		}
  141. 		if(w==n)
  142. 		{
  143. 		printf("yes\n");
  144. 		break;
  145. 		}
  146.     	int size = n;
  147.     	if(sum%k!=0)
  148.     	{
  149.     	printf("no\n");
  150.     	break;
  151.     	}
  152.        //checkDuplicates1(weights,n);
  153.        int target = sum/k;
  154. 	   generateSubsets(weights,n,target);
  155.        v.clear();
  156. 	if(flag==1 && a==n)
  157. 	printf("yes\n");
  158. 	else
  159. 	printf("no\n");
  160.     //printf("Nodes generated %d\n", total_nodes);
  161.     T--;
  162. 	}
  163.     return 0;
  164. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
1
10 5
1 2 3 4 5 6 7 8 9 10
stdout
copy 
1 2 3 5 
1 2 8 
1 3 7 
1 4 6 
1 10 
2 3 6 
2 4 5 
2 9 
3 8 
4 7 
5 6 
no
https://ideone.com/ML0zeR
Sanskar.
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!