JAVA 95% DP solution make a sort before can improve 4%


  • 0
    T
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        return sum % 2 == 0 && SubsetSum(nums, sum/2);
    }
    //dp[i] = dp[i - k] k is the num in nums, i <= sum && i >= k;
    private boolean SubsetSum(int[] nums, int sum) {
        boolean[] dp = new boolean[sum + 1];
        Arrays.sort(nums);//advance 4%
        dp[0] = true;
        for (int k : nums) {
            if (k > sum) return false;
            if (dp[sum - k]) return true;
            System.arraycopy(dp, 0, dp, k, sum - k);
        }
        return false;
    }
    
    

Log in to reply
 

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