Partition Equal Subset Sum

Partition Equal Subset Sum:

Problem Description:

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.


Example 1:

Input: nums = [1,5,11,5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].


Example 2:

Input: nums = [1,2,3,5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

 

Constraints:

1 <= nums.length <= 200

1 <= nums[i] <= 100


Solution:


class Solution {

    public boolean canPartition(int[] nums) {

        int totalsum = 0, subsetsum = 0;

        for(int num: nums)

            totalsum+=num;

        if(totalsum%2 == 0)

            subsetsum = totalsum/2;

        else return false;

        int n = nums.length;

        boolean[][] k = new boolean[n+1][subsetsum+1];

        k[0][0] = true;

        for(int i=1; i<=n;i++)

        {

            k[i][0] = true;

        }

        for(int j=1; j<=subsetsum;j++)

        {

            k[0][j] = false;

        }

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=subsetsum; j++)

            {

                if(j<nums[i-1])

                    k[i][j] = k[i-1][j];

                else

                {

                    k[i][j] = ( k[i-1][j] ||  k[i-1][j-nums[i-1]]);

                }

            }

        }

        return k[n][subsetsum];

    }

}


Output:


Input: nums = [1,5,11,5]

Output: true


Reference:  👉 Partition Equal Subset Sum

                                                                    Happy Coding 💻 :-)
















Comments

Post a Comment

Popular posts from this blog

Valid Username Regular Expression

Valid Username Regular Expression: Problem Description: You are updating the username policy on your company's internal networking platform. According to the policy, a username is considered valid if all the following constraints are satisfied: The username consists of 8 to 30 characters inclusive. If the username consists of less than  or greater than 8 characters, then it is an invalid username. The username can only contain alphanumeric characters and underscores (_). Alphanumeric characters describe the character set consisting of lowercase characters[a-z] , uppercase characters[A-Z] , and digits[0-9]. The first character of the username must be an alphabetic character, i.e., either lowercase character [a-z] or uppercase character [A-Z]. Update the value of regularExpression field in the UsernameValidator class so that the regular expression only matches with valid usernames. Input Format The first line of input contains an integer , describing the total number of usernames. Ea...
Read more

Rotate String in Right Direction in java

Rotate String in Right Direction in java: Program: import java.util.*; public class RotateString { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); char[] ch = new char[n]; for(int i=0;i<n;i++) { ch[i] = s.next().charAt(0); } int r = s.nextInt(); char temp = 'a'; r=r%n; while(r>0) { temp = ch[n-1]; for(int i = n-1; i>0;i--) { ch[i] = ch[i-1]; } ch[0] = temp; System.out.println("r: " + r); for(int i=0;i<n;i++) { System.out.print(ch[i]); } System.out.println(); r--; } for(int i=0;i<n;i++) { System.out.print(ch[i]); } } } Output : 5 a s d f g 3 r: 3 gasdf r: 2 fgasd r: 1 dfgas dfgas                                                            Happy Coding 💻:-)
Read more

Sum of Elements of Lower Triangular Matrix

Sum of Elements of Lower Triangular Matrix: Program: import java.util.Scanner; public class LowerTriangularElementsSum { public static void main(String[] args) { int r, c; Scanner s = new Scanner(System.in); r = s.nextInt(); c = s.nextInt(); if(r!=c) { System.exit(0); } int[][] matrix = new int[r][c]; for(int i = 0; i<r; i++) { for(int j = 0; j<c;j++) { matrix[i][j] = s.nextInt(); } } int sum = 0; for(int i = 0; i<r; i++) { for(int j = 0;j<c; j++) { if(i>=j) { System.out.print(matrix[i][j]); System.out.print(" "); sum+=matrix[i][j]; } } } System.out.println("\nThe sum of Lower triangular elements of a matrix is: " + sum); } } /* In other words, a square matrix is lower triangular if all its entries above the main diagonal are zero.  * Example of a 3 × 3 lower triangular matrix: Diagonal matrices are both upper  *and lower triangular since they have zeroes a...
Read more