编程题：输入n个数，判断其中是否有k个数的和等于m

╰+哭是因爲堅強的太久メ 2022-05-28 10:35 171阅读 0赞

描述：输入n个数，判断其中是否有k个数的和等于m，如果有，输出“perfect”;否则，输出“good”。

案例一：

输入：5 100

10 20 30 40 50

输出：perfect

案例二：

输入：5 100

10 40 70 86 120

输出：good

程序如下：

package package1;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    
    public class Main {
    	
    	public static void main(String[] args)
    	{
    		Scanner sc =new Scanner(System.in);	
    		int n=0;
    		int m=0;
    		String[] str=sc.nextLine().trim().split(" ");
    		for(int i=0;i<2;i++)
    		{
    			n =Integer.parseInt(str[0]);
    			m =Integer.parseInt(str[1]);
    		}
    		
    		//获取第二行输入的数据
    		String[] str1=sc.nextLine().trim().split(" ");	
    		List<Integer> beginList=new ArrayList<Integer>();
    		for(int i=0;i<str1.length;i++)
    		{
    			beginList.add(Integer.parseInt(str1[i]));
    		}
    		
    		//去除大于m的数据
    		for(int i=0;i<beginList.size();i++)
    		{
    			if(beginList.get(i)>m)
    			{
    				beginList.remove(beginList.get(i));
    			}
    		}
    		/*
    		//数组排序，从最小到最大
    		int temp=0;
    		for(int i=0;i<n;i++)
    		{
    			for(int j=i+1;j<n;j++)
    			{
    				if(beginList.get(i)>beginList.get(j))
    				{
    					temp=beginList.get(j);
    					beginList.set(j, beginList.get(i));
    					beginList.set(j, temp);
    				}
    			}
    		}
    		*/	
    		List<Integer> list=new ArrayList<Integer>();
    		try {
    			boolean flag =ComputeSum(0,beginList,list,m);
    			if(!flag)
    			{
    				System.out.println("good");
    			}	
    		} catch (RuntimeException e) {
    			// TODO Auto-generated catch block
    			System.out.println("perfect");
    			
    		}
    		
    	}	
    	
    	//利用递归形式的回溯算法
    	public static boolean ComputeSum(int i,List<Integer> beginList,List<Integer> list,int m) throws RuntimeException
    	{
    		int sum=0;
    		if(i>beginList.size()-1)
    		{
    			
    			for(int j=0;j<list.size();j++)
    			{
    				sum+=list.get(j);
    			}
    			if(sum==m)
    			{
    				//通过抛出异常来结束递归调用
    				throw new RuntimeException();
    			}
    		}else
    		{
    			list.add(beginList.get(i));
    			ComputeSum(i+1,beginList,list,m);
    			list.remove(beginList.get(i));
    			ComputeSum(i+1,beginList,list,m);
    		}
    		
    		return false;
    	}
    }