Cpp solution with explanation in details


  • 6

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

    Ref: http://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum/

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

  • 0
    Y
    This post is deleted!

  • 0
    A

    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)

  • 0
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    E

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

  • 0
    Z

    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 :)


  • 0

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


Log in to reply
 

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