public static boolean subsetSumToK(int n, int k, int arr[]){

        // Write your code here.

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

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

        {

            dp[i][0]=true;

        }

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

        {

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

            {

                if(j>=arr[i-1])

                {

                    dp[i][j]=dp[i-1][j]||dp[i-1][j-arr[i-1]];

                }

                else

                {

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

                }

            }

        }

        return dp[n][k];

    }

public static void insertionSort(int[] arr, int size) {

        //Your code goes here

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

        {

            int x=arr[i];

            int j=i-1;

            while(j>=0&&arr[j]>x)

            {

                arr[j+1]=arr[j];

                j--;

            }

            arr[j+1]=x;

        }

    }

public static ArrayList<Integer> zigzagTreeTraversal(TreeNode<Integer> root) 

    {

        //    Write your code here.

        ArrayList<Integer>ans=new ArrayList<>();

        LinkedList<TreeNode<Integer>>ll=new LinkedList<>();

        ll.add(root);

        boolean flag=false;

        while(ll.size()>0)

        {

            int n=ll.size();

            ArrayList<Integer>al=new ArrayList<>();

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

            {

                root=ll.poll();

                if(root.left!=null)

                {

                    ll.add(root.left);

                }

                if(root.right!=null)

                {

                    ll.add(root.right);

                }

                al.add(root.data);

            }

            if(flag==false)

            {

                ans.addAll(al);

                flag=true;

            }

            else

            {

                Collections.reverse(al);

                ans.addAll(al);

                flag=false;

            }

        }

        return ans;

    }