Leet Code 416. Partition Equal Subset Sum

package pep.Day86;

public class LeetCode_416_Partition_Equal_Subset_Sum {
    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums));
    }

    public static boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 != 0 || n == 1) {
            return false;
        }

        return isSubsetSum_1D(n, nums, sum / 2);
    }

    // METHOD 1- Using 2D Array
    public static boolean isSubsetSum(int n, int arr[], int sum) {
        boolean[][] dp = new boolean[n + 1][sum + 1];

        for (int i = 0; i <= n; i++) {
            for (int tar = 0; tar <= sum; tar++) {
                if (tar == 0)
                    dp[i][tar] = true;
                else if (i == 0)
                    dp[i][tar] = false;
                else {
                    // sirf isse case me element ko consider krenge
                    if (tar - arr[i - 1] >= 0) {

                        // item ko nhi lete hain
                        if (dp[i - 1][tar])
                            dp[i][tar] = dp[i - 1][tar];

                            // item ko lete hain
                        else if (dp[i - 1][tar - arr[i - 1]])
                            dp[i][tar] = dp[i - 1][tar - arr[i - 1]];

                    } else {
                        // exclude wala case
                        dp[i][tar] = dp[i - 1][tar];
                    }
                }
            }
        }

        return dp[n][sum];
    }






    // METHOD 2- Using 1D Array
    public static boolean isSubsetSum_1D(int n, int arr[], int sum) {
        boolean[] dp = new boolean[sum + 1];

        dp[0] = true;
        for (int num : arr) {
            for (int tar = sum; tar > 0; tar--) {
                if (tar - num >= 0)
                    dp[tar] = dp[tar - num] || dp[tar];
            }

            if (dp[sum] == true)
                return dp[sum];
        }

        return dp[sum];
    }


}