fork download
copy 
  1. // Returns true if there exists a subset 
  2. // with given sum in arr[] 
  3. #include <stdio.h> 
  4. #include <stdbool.h> 
  5.  
  6. bool isSubsetSum(int arr[], int n, int sum) 
  7. { 
  8. 	// The value of subset[i%2][j] will be true 
  9. 	// if there exists a subset of sum j in 
  10. 	// arr[0, 1, ...., i-1] 
  11. 	bool subset[2][sum + 1]; 
  12.  
  13. 	for (int i = 0; i <= n; i++) { 
  14. 		for (int j = 0; j <= sum; j++) { 
  15.  
  16. 			// A subset with sum 0 is always possible 
  17. 			if (j == 0) 
  18. 				subset[i % 2][j] = true; 
  19.  
  20. 			// If there exists no element no sum 
  21. 			// is possible 
  22. 			else if (i == 0) 
  23. 				subset[i % 2][j] = false; 
  24. 			else if (arr[i - 1] <= j) 
  25. 				subset[i % 2][j] = subset[(i + 1) % 2] 
  26. 			[j - arr[i - 1]] || subset[(i + 1) % 2][j]; 
  27. 			else
  28. 				subset[i % 2][j] = subset[(i + 1) % 2][j]; 
  29. 		} 
  30. 	} 
  31.  
  32. 	return subset[n % 2][sum]; 
  33. } 
  34.  
  35. // Driver code 
  36. int main() 
  37. { 
  38. 	int arr[] = { 6, 2, 5 }; 
  39. 	int sum = 7; 
  40. 	int n = sizeof(arr) / sizeof(arr[0]); 
  41. 	if (isSubsetSum(arr, n, sum) == true) 
  42. 		printf("There exists a subset with given sum"); 
  43. 	else
  44. 		printf("No subset exists with given sum"); 
  45. 	return 0; 
  46. } 
  47.  
Success #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
There exists a subset with given sum
https://ideone.com/xuM8GT
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!