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


  • 0

    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;
    }

Log in to reply
 

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