fork download
copy 
  1. //https://l...content-available-to-author-only...e.com/problems/partition-to-k-equal-sum-subsets/
  2.  
  3. #include <iostream>
  4. #include <string>
  5. #include <vector>
  6. #include <set>
  7. #include <bitset>
  8. #include <numeric>
  9. #include <algorithm>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. using namespace std;
  13.  
  14. template<typename T>
  15. void print(T& container)
  16. {
  17. 	for (auto num : container)
  18. 	{
  19. 		cout << num << "\n";
  20. 	}
  21. 	cout << endl;
  22. }
  23.  
  24. #define max_size 17
  25.  
  26. class Solution {
  27. 	vector<bool> visited;
  28. public:
  29. 	bool canPartitionKSubsets(vector<int>& nums, int k) 
  30. 	{
  31. 		// not enough nums to put atleast one in each 'k' bucket
  32. 		if (nums.size() < k)
  33. 			return false;
  34.  
  35. 		// check if it is possible to divide the total sum into k partition (bucket)
  36. 		int total_sum = std::accumulate(nums.begin(), nums.end(), 0);
  37. 		if (total_sum % k != 0)
  38. 			return false;
  39.  
  40. 		visited.resize(max_size, false);
  41. 		return canPartitionKSubsetsHelper(nums, visited, k, 0, 0, total_sum / k);
  42. 	}
  43.  
  44. 	bool canPartitionKSubsetsHelper(vector<int>& nums, vector<bool>& visited, int k, int start, int currSum, int targetSum)
  45. 	{
  46. 		//cout << k << " " << currSum << endl;
  47. 		// all 'k' buckets can be filled with the target sum
  48. 		if (k == 0)
  49. 			return true;
  50.  
  51. 		// if 'k' is filled with the target sum, recurse it for 'k-1' bucket.
  52. 		if (currSum == targetSum)
  53. 			return canPartitionKSubsetsHelper(nums, visited, k - 1, start, 0, targetSum);
  54.  
  55. 		//invalid configuration
  56. 		if (currSum > targetSum)
  57. 			return false;
  58.  
  59. 		for (int i = start; i < nums.size(); i++)
  60. 		{
  61. 			visited[i] = true;
  62. 			if (canPartitionKSubsetsHelper(nums, visited, k, start + 1, currSum + nums[i], targetSum))
  63. 				return true;
  64. 			visited[i] = false;
  65. 		}
  66. 		return false;
  67. 	}
  68. };
  69.  
  70. int main()
  71. {
  72. 	Solution sln;
  73. 	vector<int> vec = { 1, 1, 1, 1, 2, 2, 2, 2 };
  74. 	cout << sln.canPartitionKSubsets(vec, 4) << endl;
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 5424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QGKlCJ
language:
C++ (gcc 8.3)
created:
2 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!