# Cpp solution with explanation in details

• It's a very classical question.
Pay attention to the note:
`1 <= k <= len(nums) <= 16`
`0 < nums[i] < 10000`

``````class Solution {
public:

//  Method returns true if nums can be partitioned into K subsets
// with equal sum
bool canPartitionKSubsets(vector<int>& nums, int K)
{
int N = nums.size();
//  If K is 1, then complete array will be our answer
if (K == 1) return true;

//  If total number of partitions are more than N, then
// division is not possible
if (N < K) return false;

// if array sum is not divisible by K then we can't divide
// array into K partitions
int sum = 0;
for (int i = 0; i < N; i++) sum += nums[i];
if (sum % K != 0) return false;

//  the sum of each subset should be subset (= sum / K)
int subset = sum / K;
int subsetSum[K];
bool taken[N];

//  Initialize sum of each subset from 0
for (int i = 0; i < K; i++) subsetSum[i] = 0;

//  mark all elements as not taken
for (int i = 0; i < N; i++) taken[i] = false;

// initialize first subsubset sum as last element of
// array and mark that as taken
subsetSum[0] = nums[N - 1];
taken[N - 1] = true;

//  call recursive method to check K-substitution condition
return canPartitionKSubsets(nums, subsetSum, taken, subset, K, N, 0, N - 1);
}

// Recursive Utility method to check K equal sum
// subsetition of array
/**
array           - given input array
subsetSum array   - sum to store each subset of the array
taken           - boolean array to check whether element
is taken into sum partition or not
K               - number of partitions needed
N               - total number of element in array
curIdx          - current subsetSum index
limitIdx        - lastIdx from where array element should be taken
*/
bool canPartitionKSubsets(vector<int>& nums, int subsetSum[], bool taken[], int subset, int K, int N, int curIdx, int limitIdx) {
if (subsetSum[curIdx] == subset) {
/*  current index (K - 2) represents (K - 1) subsets of equal
sum last partition will already remain with sum 'subset'*/
if (curIdx == K - 2) return true;

//  recursive call for next subsetition
return canPartitionKSubsets(nums, subsetSum, taken, subset,
K, N, curIdx + 1, N - 1);
}

//  start from limitIdx and include elements into current partition
for (int i = limitIdx; i >= 0; i--) {
//  if already taken, continue
if (taken[i]) continue;
int tmp = subsetSum[curIdx] + nums[i];

// if temp is less than subset then only include the element
// and call recursively
if (tmp <= subset) {
//  mark the element and include into current partition sum
taken[i] = true;
subsetSum[curIdx] += nums[i];
bool nxt = canPartitionKSubsets(nums, subsetSum, taken, subset, K, N, curIdx, i - 1);
// after recursive call unmark the element and remove from
// subsetition sum
taken[i] = false;
subsetSum[curIdx] -= nums[i];
if (nxt) return true;
}
}
return false;
}

};``````

• This post is deleted!

• Same solution in python:

``````    def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""

def canPartitionKSubsets(nums, subS, taken, Sk, K, N, curIdx, limitIdx):
if subS[curIdx] == Sk:
if curIdx == K - 2:
return True
return canPartitionKSubsets(nums, subS, taken, Sk, K, N, curIdx+1, N-1)

for i in xrange(limitIdx, -1, -1):
if taken[i]: continue
tmp = subS[curIdx] + nums[i]
if tmp <= Sk:
taken[i] = True
subS[curIdx] += nums[i]
nxt = canPartitionKSubsets(nums, subS, taken, Sk, K, N, curIdx, i-1)
taken[i] = False
subS[curIdx] -= nums[i]
if nxt: return True
return False

N = len(nums)
if k == 1: return True
if N < k: return False
S = sum(nums)
if S % k != 0: return False
Sk = S/k
subS = [0]*N
taken = [False]*N
subS[0] = nums[N-1]
taken[N-1] = True
return canPartitionKSubsets(nums, subS, taken, Sk, k, N, 0, N-1)``````

• This post is deleted!

• This post is deleted!

• Thanks for such great solution,
I think there are some steps can be promoted to code more concisely.

``````#1 Last part of recursion and check can be merged like this:
//bool nxt = canPartitionKSubsets(nums, subsetSum, taken, subset, K, N, curIdx, i - 1);
if(canPartitionKSubsets(nums,subsetSum,taken,subset,K,N,curIdx,i-1))return true;
taken[i] = false;
subsetSum[curIdx] -= nums[i];
//if (nxt) return true;

#2 variable 'tmp' can be omitted and change into this:
//int tmp = subsetSum[curIdx] + nums[i];
if ((subsetSum[curIdx]+=nums[i])<= subset) {
taken[i] = true;
//subsetSum[curIdx] += nums[i];
if(canPartitionKSubsets(nums, subsetSum, taken, subset, K, N, curIdx, i + 1))return true;
taken[i] = false;
//subsetSum[curIdx] -= nums[i];
}
subsetSum[curIdx] -= nums[i];
``````

Furthermore,traverse nums from front to back is also AC:

``````#Last version like this:
bool canPartitionKSubsets(vector<int>& nums, int K)
{
int N = nums.size();
if (K == 1) return true;
if (N < K) return false;
int sum = 0;
for (int i = 0; i < N; i++) sum += nums[i];
if (sum % K != 0) return false;
int subset = sum / K;
int subsetSum[K];
bool taken[N];
for (int i = 0; i < K; i++) subsetSum[i] = 0;
for (int i = 0; i < N; i++) taken[i] = false;
subsetSum[0] = nums[N - 1];
taken[N - 1] = true;
//traverse nums from front to back
return canPartitionKSubsets(nums, subsetSum, taken, subset, K, N, 0, 0);
}
bool canPartitionKSubsets(vector<int>& nums, int subsetSum[], bool taken[], int subset, int K, int N, int curIdx, int i) {
if (subsetSum[curIdx] == subset) {
if (curIdx == K - 2) return true;
//traverse nums from begin again.
return canPartitionKSubsets(nums, subsetSum, taken, subset,
K, N, curIdx + 1, 0);
}
for(;i<N;i++){
//if (taken[i]) continue; //this can be merged either.
if ((subsetSum[curIdx]+=nums[i])<= subset && !taken[i]) {
taken[i] = true;
if(canPartitionKSubsets(nums, subsetSum, taken, subset, K, N, curIdx, i + 1))return true;
taken[i] = false;
}
subsetSum[curIdx] -= nums[i];
}
return false;
}
``````

• This solution is not completely right.

Say the input `nums = [-1, -1, -1, 1]` and `K = 2`, the expected output is `true`, while the output of this implementation is `false`.

The problem is the conditional statement `if (tmp <= subset)` is not correct, which assumes there is no negative elements in the given input. Once we remove this statement, this implementation is right :)

• @zhutou7
It says `0 < nums[i] < 10000` .

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.