JAVA Accepted DP & DFS solution with newly updated test case covered


  • 0

    Since test cases have been updated, my original 7ms DFS got TLE for long input, and my original passed DP solution now fails at one case: [2,2,3,5] (i think it is newly added). But by looping from tail to head the DP solution got Accepted. DFS solution got updated as well. Code attached.

    DP

    public class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length == 0) return false;
            int sum = 0;
            for (int num : nums) sum += num;
            if (sum % 2 == 1) return false;
            sum /= 2;
            Arrays.sort(nums);
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            int currSum = 0;
            for (int num : nums) {
                currSum += num;
                for (int i = Math.min(currSum, sum); i >= num; i--) {
                    dp[i] |= dp[i - num];
                }
            }
            return dp[sum];
        }
    }
    

    DFS

    public class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length == 0) return false;
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 2 == 1) return false; // important
            sum /= 2;
            
            Arrays.sort(nums);
            return dfs(nums, nums.length - 1, sum);
        }
        private boolean dfs(int[] nums, int index, int target) {
            if (target < 0) return false;
            if (target == 0) return true;
            for (int i = index; i >= 0; i--) {
                if (dfs(nums, i - 1, target - nums[i])) return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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