# C iterative solution, 9ms original order(no sorting), explained

• This algorithm uses a stack-based DFS to first find all the subsets that can combine into the division value (sum / k). Then it uses DFS again trying to chain disjoint subsets up into the original set. If the chaining is successful, that would make a valid solution.

In special situations in which we have a large number of subsets that add to the division value, it may exceed O(n), but in most cases the main algorithm runs on O(n) space.

``````int sumArr(int* nums, int numsSize)
{
int sumArray = 0;
for (int i = 0; i < numsSize; i++)
sumArray += nums[i];
return sumArray;
}

int arrToInt(int size, int* arr, int len)       //build a bit array from the array
{
int result = (1 << size) - 1;
for (int i = 1; i < len; i++)
result &= ~(1 << arr[i]);
return result;
}

// Find subsets that can combine into the desired value
int* findSum(int* nums, int size, int div, int* count)
{
int capacity = size;
int* combinations = (int*)malloc(capacity * sizeof(*combinations));
*count = 0;
int* stack = (int*)malloc((size + 1) * sizeof(*stack));
int* choices = (int*)malloc((size + 1) * sizeof(*choices));
for (int i = 0; i < size + 1; i++)
choices[i] = i;
int p = 0;
stack[p++] = -1;
int sum = 0;
while (p)
{
if (sum < div && choices[stack[p - 1] + 1] < size)
{
stack[p] = choices[stack[p - 1] + 1];         //push into stack
sum += nums[stack[p]];
choices[stack[p - 1] + 1]++;
p++;
}
else
{
if (sum == div)
{
if (*count == capacity)          //expand if full
{
capacity <<= 1;
int* tmp = (int*)realloc((void*)combinations, capacity * sizeof(*combinations));
if (!tmp)
{
printf("Realloc error in findSum at capacity = %d\n", capacity);
return NULL;
}
combinations = tmp;
}
combinations[(*count)++] = arrToInt(size, stack, p);
}
if (p == 0)
break;
sum -= nums[stack[p - 1]];                 //pop from stack
choices[stack[p - 1] + 1] = stack[p - 1] + 1;
p--;
}
}
free(stack);
free(choices);
return combinations;
}

// Attempt to chain up the subsets into the original set
bool findChain(int* combinations, int count, int size, int k)
{
int full = (1 << size) - 1;
int* stack = (int*)malloc((k + 1) * sizeof(*stack));
int* choices = (int*)malloc((count + 1) * sizeof(*choices));
int* accumulate = (int*)malloc((k + 1) * sizeof(*accumulate));
accumulate[0] = -1;
for (int i = 0; i < count + 1; i++)
choices[i] = i;
int p = 0;
stack[p++] = -1;
while (p)
{
if (p < k + 1 && choices[stack[p - 1] + 1] < count)
{
if (accumulate[p - 1] | combinations[choices[stack[p - 1] + 1]] == full)      // if the subset is disjoint
{
stack[p] = choices[stack[p - 1] + 1];              //push into stack
accumulate[p] = accumulate[p - 1] & combinations[stack[p]];
choices[stack[p - 1] + 1]++;
p++;
}
else
choices[stack[p - 1] + 1]++;
}
else
{
if (p == k + 1 && accumulate[p - 1] == 0)
return 1;        // The subsets combined into the original set
choices[stack[p - 1] + 1] = stack[p - 1] + 1;
p--;      //not successful, pop from stack
}
}
free(stack);
free(choices);
free(accumulate);
return 0;
}

bool canPartitionKSubsets(int* nums, int numsSize, int k)
{
if (k == 1 && k == numsSize)
return 1;
int sum = sumArr(nums, numsSize);
if (sum % k)
return 0;
int div = sum / k;
int* smallNum = (int*)malloc(numsSize * sizeof(*smallNum));
int p = 0;
int size = numsSize;
for (int i = 0; i < numsSize; i++)
{
if (nums[i] > div)
return 0;
// If element already reaches the division sum, it is automatically a subset, no need to further analyse
if (nums[i] == div)
{
k--;
size--;
}
else
smallNum[p++] = nums[i];
}
int count = 0;
int* combinations = findSum(smallNum, size, div, &count);
if (count < k)
return 0;
bool found = findChain(combinations, count, size, k);
free(combinations);
return found;
}``````

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