Subset Sum with Recursion | memorization | DP

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

https://www.geeksforgeeks.org/subset-sum-problem-dp-25/

            Recursion                                     

     class Solution {

    

    static boolean isSumK(int[] nums, int curin, int curSum) {

        

        if(curSum==0) {

            return true;

        }

        

        if(curin<0) {

            return false;

        }

        

        return isSumK(nums, curin-1, curSum-nums[curin]) 

            || isSumK(nums, curin-1, curSum);

    }

With Memorization

class Solution{

    static int issum(int arr[], int indx, int sum, int dp[][]) {

        

        if(sum==0)

         return 1;

         

        if(indx<0)

         return 0;

        

        if(dp[indx][sum]!=-1)

         return dp[indx][sum];

         

        int pick = 0;

        if(sum>=arr[indx]) 

          pick = issum(arr, indx-1, sum-arr[indx],dp);

          

        int notpick = issum(arr, indx-1, sum,dp);

        

        if(pick==1 || notpick==1) 

         return dp[indx][sum] = 1;

         

        return dp[indx][sum] = 0;

    }

Subset sum K [Recursion]

 https://www.geeksforgeeks.org/subset-sum-problem-dp-25/

class Solution {

    

    static boolean isSumK(int[] nums, int curin, int curSum) {

        

        if(curSum==0) {

            return true;

        }

        

        if(curin<0) {

            return false;

        }

        

        return isSumK(nums, curin-1, curSum-nums[curin]) 

            || isSumK(nums, curin-1, curSum);

    }

    static Boolean isSubsetSum(int N, int arr[], int sum) {

        // code here

        return isSumK(arr, N-1, sum);

    }

}

Java Practice [HashMap]

Group Anagrams https://leetcode.com/problems/group-anagrams/

 class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {

        

        HashMap<String, List<String>> hm = new HashMap<>();

        

        for(int i=0;i<strs.length;i++) {

            char[] s = strs[i].toCharArray();

            Arrays.sort(s);

            String k = new String(s);

            if(hm.containsKey(k)) {

                hm.get(k).add(strs[i]);

            } else {

                List<String> ls = new ArrayList<String>();

                ls.add(strs[i]);

                hm.put(k,ls);

            }

        }

        

        List<List<String>> ans = new ArrayList<List<String>>();;

        

        for (String p:hm.keySet()) {

          ans.add(hm.get(p));   

        }

        

        return ans;

    }

}

Linked List in Java without Collections

• Linked List in Java without Collections

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

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

        Node n1 = new Node(5);
        Node n2 = new Node(6);
        Node n3 = new Node(7);
        Node n4 = new Node(8);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        Node start  = n1;
        while(start!=null) {
          System.out.println(start.data+" ");
          start = start.next;
        }
    }
}