编程题：从n个数中选取m个数，计算m个数的和s，判断剩余n-m个数中是否存在等于s的数，如果存在，输出最大值

分手后的思念是犯贱 2022-05-28 11:13 181阅读 0赞

描述：从n个数中选取m个数，计算m个数的和s，判断剩余n-m个数中是否存在等于s的数，如果存在，输出最大值。第一行输入n和m值，第二行输入n个数，输出最大值。

例如：

输入：6 2

1 2 5 3 7 4

输出：7

分析：1+2=3；2+5=7；2+3=5；3+4=7；1+3=4；1+4=5 其中最大值为7

代码如下：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    public class Main
    {
    	
    	public static int maxSum;
    	public static int index;
    	
        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]));
    		}	
    		//数组排序，从最小到最大
    		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(i, temp);
    				}
    			}
    		}
    		
    		int[] iTemp=new int[m];
    		computeNum(beginList,n,m,0,iTemp,0);
    		//打印结果值
    		System.out.println(maxSum);
    		
    		
        }
        //从n个数中选m个数，使其和等于剩余n-m数中的数，输出最大数
        public static void computeNum(List<Integer> originList,int n,int m,int startIndex,int[] iTemp,int arrIndex)
        {    
        	int sum=0;
        	if(m==0)
        	{		
        		for(int j=index+1;j<n;j++)
        		{
        			for(int i=0;i<iTemp.length;i++)   //计算m个值的和
        			{
        				sum+=iTemp[i];
        			}
        			if(sum==originList.get(j))
        			{
        				maxSum=originList.get(j);
        				break;
        			}else if(sum<originList.get(j))   //如果小于，之后就不要考虑了了，结束循环
        			{
        				break;
        			}
        		}
        		
    		}else
    		{
    			//递归遍历，从n个数选m个数的组合
    			int endIndex=n-m;
    	    	for(int i=startIndex;i<=endIndex;i++)
    	    	{
    	    		iTemp[arrIndex]=originList.get(i);
    	    		index=i;
    	    		computeNum(originList,n,m-1,i+1,iTemp,arrIndex+1);
    	    	}
    		}
        	
         }
    }

package myPackage;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    public class Main
    {
    	
    	public static int maxSum;
    	public static int index;
    	
        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]));
    		}	
    		//数组排序，从最小到最大
    		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(i, temp);
    				}
    			}
    		}
    		
    		List<Integer> iTemp =new ArrayList<Integer>();
    		computeNum(beginList,n,m,0,iTemp);
    		//打印结果值
    		System.out.println(maxSum);
    		
    		
        }
        //从n个数中选m个数，使其和等于剩余n-m数中的数，输出最大数
        public static void computeNum(List<Integer> originList,int n,int m,int startIndex,List<Integer> iTemp)
        {    
        	int sum=0;
        	if(m==0)
        	{		
        		for(int j=index+1;j<n;j++)
        		{
        			for(int i=0;i<iTemp.size();i++)   //计算m个值的和
        			{
        				sum+=iTemp.get(i);
        			}
        			if(sum==originList.get(j))
        			{
        				maxSum=originList.get(j);
        				break;
        			}else if(sum<originList.get(j))   //如果小于，之后就不要考虑了了，结束循环
        			{
        				break;
        			}
        		}
        		
    		}else
    		{
    			//递归遍历，从n个数选m个数的组合
    			int endIndex=n-m;
    	    	for(int i=startIndex;i<=endIndex;i++)
    	    	{
    	    		iTemp.add(originList.get(i));
    	    		index=i;
    	    		computeNum(originList,n,m-1,i+1,iTemp);
    	    		iTemp.remove(iTemp.size()-1);
    	    	}
    		}
        	
         }
    }