Java solutions with dynamic programming and DFS


  • 1
    Y

    First, calculate the sum of all.
    Second, if sum is odd, could not split the array.
    Then, using dynamic programming, check whether we could generate subarray accumulating to sum / 2. dp[num][j] means whether we could create a subarray of items 1 ... j with the sum as "num".
    Final, return dp[sum / 2][n].

        public boolean canPartition (int[] nums) {
            int n = nums.length;
            int sum = 0;
            
            for (int i = 0; i < n; i++)
                sum += nums[i];
     
            if (sum % 2 != 0)
                return false;
     
            boolean dp[][]=new boolean[sum / 2 + 1][n + 1];
     
            for (int i = 0; i <= n; i++) // with no item, we could get "0" 
                dp[0][i] = true;
     
            for (int i = 1; i <= sum / 2; i++) // w/o item, we could not get "i"
                dp[i][0] = false;
     
            for (int i = 1; i <= sum / 2; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i >= nums[j - 1])
                        dp[i][j] = dp[i][j - 1] || dp[i - nums[j - 1]][j - 1]; // with or w/o item j - 1
                    else
                        dp[i][j] = dp[i][j - 1];
                }
            }
    
            return dp[sum / 2][n];
        }
    

    The following is the solution with DFS. It's from another post but with minor updates:

    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;
    	
    	return dfs(nums, 0, sum / 2);
    	
    }
    
    public boolean dfs(int[] nums, int from, int sum) {
    	if(sum == 0)
    		return true;
    	
    	if(sum < 0)
    		return false;
    
    	for(int i = from; i < nums.length; i++)
    		if(dfs(nums, i + 1, sum - nums[i]))
    		    return true;
    	
    	return false;	
    }
    

  • 0
    R

    @yuhaowang001 said in Java solutions with dynamic programming and DFS:

    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;

    return dfs(nums, 0, sum / 2);

    }

    public boolean dfs(int[] nums, int from, int sum) {
    if(sum == 0)
    return true;

    if(sum < 0)
    return false;

    for(int i = from; i < nums.length; i++)
    if(dfs(nums, i + 1, sum - nums[i]))
    return true;

    return false;
    }

    time limit exceeded


  • 0

    Time Limit Exceeded.

    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]


  • 0
    D

    @nova0930 It seems to lead to infinite loop. Do you know why?


Log in to reply
 

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