Solve this problem with DP solution


  • -1
    L

    public bool CanPartitionKSubsets(int[] nums, int k) {

        if (nums.Length == 0 || k <= 0)
            {
                return false;
            }
    
            int sum = 0;
    
            foreach (int num in nums)
            {
                sum += num;
            }
    
            if (sum % k != 0)
            {
                return false;
            }
    
            int target = sum / k;
    
            bool[] res = new bool[target + 1];
            res[0] = true;
    
            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = target; j >= nums[i]; j--)
                {
                    res[j] = res[j] || res[j - nums[i]];
                }
            }
    
            return res[target];
    }

  • 1
    T

    This solution is wrong!

    Try this test case:
    [1,1,2,4]
    4

    The expected output is "false", but your output is "true".


Log in to reply
 

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