Java dynamic programming (fastest)


  • 4
    P

    Dynamic programming solution:
    Calculating the sum of all members in the array, and find if is there any subsets of the array has sum equal to sum/2
    The general DP formula is:

    dp[n][W] = dp[n - 1][W - a[n-1]] || dp[n - 1][W]
    

    Detail solution:

    public class Solution {
        
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            if (sum %2 != 0) return false;
            sum /= 2;
            
            boolean dp[][] = new boolean[nums.length + 1][sum + 1];
            
            for (int i = 0; i < nums.length + 1; i++) {
                for (int j = 0; j < sum + 1; j ++) {
                    if (i == 0 || j == 0)
                        dp[i][j] = false;
                }
            }
            
            dp[0][0] = true;
            
            for (int i = 1; i < nums.length + 1; i++) {
                for (int j = 1; j < sum + 1; j++) {
                    if (j >= nums[i- 1]) 
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i-1]];
                    else 
                        dp[i][j] = dp[i - 1][j];
                }
            }
            
            return dp[nums.length][sum];
        }
    }
    

  • 0
    D

    Is One Dimension Array sufficed? Is it a must to use TWO Dimension Array for this problem ?


  • 0
    P

    Intuitively I think two dimensional array makes it easy for me to understand the problem, so I go with two dimensional array.


  • 0
    D

    @phhoang :D That's fine. There are quite a few threads using the 1D array. As far as I know, they'd work as well.


  • 1

    Well done! It became the typical backpack question with your DP formula.


  • 0
    L

    Good solution.
    But I got Memory limitation exceed when 2D array. So I use 1D Array and it is accepted.

    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum & 1) return false;
            sum >>= 1;
            vector<int> dp(sum+1, false);
            dp[0] = true;
            for (int i = 1; i <= nums.size(); i++ ) {
                for (int j = sum; j >= 1; j--) {
                    if (j >= nums[i-1]) {
                        dp[j] = dp[j] || dp[j-nums[i-1]];
                    } else {
                        dp[j] = dp[j];
                    }
                }
            }
            return dp[sum];
        }
    };
    

Log in to reply
 

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