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


  • 1

    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?


  • 1
    -

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


  • 1
    X

    This solution doesn't work for this problem. Passing the last for loop in your code doesn't guarantee it to be true: being able to form subsets whose sum is sub, 2 * sub... k * sub doesn't mean that they can be achieved at the same time.

    For example, [2, 2, 2, 2, 3, 4, 5] and 4 as input, we can see there are subsets whose sum is 5, 10, 15 or 20. In your solution it would return true. Yet by simple observation we can see that there's no way we can split the array into 4 subsets whose sum is 5. (s1 = [5], s2 = [2, 3], we have 2, 2, 2, 4 left, there's no way we can make it work).


Log in to reply
 

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