# Partition to K Equal Sum Subsets in C++

C++Server Side ProgrammingProgramming

Suppose we have an array of integers called nums and a positive integer k, check whether it's possible to divide this array into k non-empty subsets whose sums are all same. So if the array is like [4,3,2,3,5,2,1] and k = 4, then the result will be True, as the given array can be divided into four subarray like [[5], [1,4], [2,3], [2,3]] with equal sums.

To solve this, we will follow these steps −

• define two table called dp and total of size 2^n,
• sort the given array nums, set sum := sum of all elements in the nums array
• if sum mod k is non 0 OR last element of nums > sum / k, then return false
• set dp[0] := true and sum := sum / k
• for i in range 0 to 2^n
• if dp[i] is non zero, then
• for j in range 0 to ,
• temp := i OR 2 ^ j
• if temp is not same as i, then
• if nums[j] <= sum – total[i] mod sum, then dp[temp] := true
• total[temp] := total[i] + nums[j]
• else come out from the loop
• return dp[(2^n) - 1]

## Example(C++)

Let us see the following implementation to get a better understanding −

Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int n = nums.size();
vector <bool> dp(1 << n);
vector <int> total(1 << n);
sort(nums.begin(), nums.end());
int sum = 0;
for(int i = 0; i < nums.size(); i++)sum += nums[i];
if(sum % k || nums[nums.size() - 1] > sum / k) return false;
dp[0] = true;
sum /= k;
for(int i = 0; i < (1 << n); i++){
if(dp[i]){
for(int j = 0; j < n; j++){
int temp = i | (1 << j);
if(temp != i){
if(nums[j] <= sum - (total[i] % sum)){
dp[temp] = true;
total[temp] = total[i] + nums[j];
}
else{
break;
}
}
}
}
}
return dp[(1 << n) - 1];
}
};
main(){
Solution ob;
vector<int> v = {4,3,2,3,5,2,1};
cout << (ob.canPartitionKSubsets(v, 4));
}

## Input

[4,3,2,3,5,2,1]
4

## Output

1
Published on 27-Feb-2020 10:42:49
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.42273861169815063, "perplexity": 6599.545883823497}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-49/segments/1637964363125.46/warc/CC-MAIN-20211204215252-20211205005252-00029.warc.gz"}