Dp solution, O(N * sum )


  • 3
    N

    class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
    int[] arr = nums;
    if(nums == null || nums.length == 0) return false;
    if(k <= 0) return false;
    if(k == 1) return true;
    int sum = 0;
    for(int i : nums){
    sum += i;
    }
    if(sum % k != 0) return false;
    int n = nums.length;
    boolean[][] dp = new boolean[sum + 1][n + 1];
    Arrays.fill(dp[0], true);
    for(int i = 1; i <= sum; i++){
    for(int j = 1; j <= n; j++){
    dp[i][j] = dp[i][j - 1];
    if(i >= arr[j - 1])
    dp[i][j] |= dp[i - arr[j - 1]][j - 1];
    }
    }
    int sub = sum / k;
    for(int i = 0; i <= sum; i += sub){
    if(dp[i][n] == false) return false;
    }
    return true;
    }
    }


  • 0
    T

    This solution is wrong!

    Try these test cases:
    [7,2,2,2,2,2,2,2,3]
    3
    [1,1,2,4]
    4

    Both cases should return "false", but your code returns "true"


  • 0
    D

    @ngoc_lam
    Seems there is a small problem, "dp[i][n] (i = 1sum/k, 2sum/k,..., (k-1)*sum/k) are all true" is a necessary condition of the problem, not a sufficient one.
    for example, the input (2,2,3,3,3,3) 4, the array cannot be divided into 4 subsets with equal sum, but the algorithm will output true.


  • 0
    N

    @Dshinji said in Dp solution, O(N * sum ):

    @ngoc_lam
    Seems there is a small problem, "dp[i][n] (i = 1sum/k, 2sum/k,..., (k-1)*sum/k) are all true" is a necessary condition of the problem, not a sufficient one.
    for example, the input (2,2,3,3,3,3) 4, the array cannot be divided into 4 subsets with equal sum, but the algorithm will output true.

    Yeah! I have sent an email to admin, now they fixed it ==)


  • 0
    D

    Nice~
    Any adjusted dp solution to completely solve the problem?


  • 0
    -

    [2,2,2,2,3,4,5]
    4
    I dont think its working for this either.


Log in to reply
 

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