Buckle exercise - 32 divided into k equal subsets

32 Divided into k Equal subsets

1. Problem description
Given an array of integers nums And a positive integer k, Find out if it is possible to divide this array into k A non empty subset , The sum is equal to .

Example 1：

Input ： nums = [4, 3, 2, 3, 5, 2, 1], k = 4

Output ： True

explain ： It is possible to divide it into 4 A subset of （5）,（1,4）,（2,3）,（2,3） Equal to the sum .
2. Enter description
First type nums Length of array n,

Then input n It's an integer , Space off .

Last input k.

1 <= k <= n <= 16

0 < nums[i] < 10000
3. The output shows that
Output true or false
4. Example
Input
7
4 3 2 3 5 2 1
4
Output
true
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<stack>
using namespace std;

bool backtracking(vector<int>nums, vector<int>edges, int len, int index)
{
    
	if (index == nums.size())
		return true;                                          
	                                                       
	for (int i = 0; i < edges.size(); i++)
	{
    
		if (nums[index] + edges[i] > len)
			continue;
		if (i > 0 && edges[i] == edges[i - 1])
			continue;

		edges[i] += nums[index];

		if (backtracking(nums, edges, len, index + 1))
			return true;

		edges[i] -= nums[index];// to flash back 
	}
	return false;
}


bool canPartitionKSubsets(vector<int>& nums, int k)
{
    
	//1. The total length is less than k
	if (nums.size() < k)
		return false;
	//2. Calculate the total length len ,len  Must be k Integer multiple 
	int len = 0;
	for (int num : nums)
		len += num;
	if (len%k != 0)
		return false;
	//3.
	int single_length = len / k;// Calculate the length of a single interval 
	vector<int>edges(k);
	sort(nums.begin(), nums.end(), greater<int>());// Sort from large to small 
    
	//4. to flash back 
	return backtracking(nums, edges, single_length, 0);


	
}
 
int main()

{
    
	vector<int>nums;
	int n, k,temp;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
    
		cin >> temp;
		nums.push_back(temp);
	}
	cin >> k;
	bool res = canPartitionKSubsets(nums, k);
	cout << (res ? "true" : "false") << endl;
	return 0;

}