Payingup:practice problem help me!

general
1

whats wrong with this code

my solution https://www.codechef.com/viewsolution/18807186

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main {

public static void main(String[] args)

	{
		Scanner one = new Scanner(System.in);
		
		int t = one.nextInt();
		
		for(int i=0;i<t;i++)
		{
			int n = one.nextInt();
			int m = one.nextInt();
			String fn = "NO";
			ArrayList<Integer> two = new ArrayList<Integer>();
			for(int k=0;k<n;k++)
			{
				int o = one.nextInt();
				two.add(o);
			}
			
			Collections.sort(two);
			int f = 0;
			int g = 0;
			for(int j=two.size()-1;j>=0;j--)
			{
				f = two.get(j);
				if((f+g)<=m)
				{
					
					g=g+f;
					if(g==m)
					{
						fn = "YES";
						break;
					}
				}
				
			}
			System.out.println(fn);
		}
		
		one.close();
	}

}

2

1

5 100

34 12 62 50 16

Your code failed for this one. Now lets see what you are doing. You are sorting and then iterating and applying a greedy approach.
Now when you sort the above array, it becomes-> 12 16 34 50 62

Your code will add 62 and after that it will add 34 and g=96 and will print No whereas there is a solution 50+34+16=100

Look at the constraints on n. It is given n<=20 so at max there can be 2^20 combinations which is approx 10^6. So you can simply generate all the combinations and check whether the sum is equal to m or not.

3

okay thanks

4

accept answer of people instead of saying thanks… :slight_smile:

5

yeah it’s called bit masking…

1 Like
6

Okayy…Thanks buddy!!