Subset Sum Problem

package pep.Day86;

public class Subset_Sum_Problem {
    public static void main(String[] args) {

    }

    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];
    }


}