7.5 dfs竞赛题----部分和(挑战程序设计竞赛)

news/2024/7/19 11:25:31 标签: dfs, 列表, 数据结构

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n; //元素个数
	static int[] a; //元素数组
	static int k; //需得到的数字
	static ArrayList<Integer> res = new ArrayList();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		k=sc.nextInt();
		Arrays.sort(a);
		dfs(k,0);//求和k,从数组a的第一个元素开始查找
	}
	/*
	 * x:当前需要得到的和
	 * cur:当前加入的元素a[cur]
	 * (1)如果当前x<0 或者 下标cur==数组a的长度,就结束
	 * (2)有两种选择
	 * 	  1.不要当前的元素a[cur]
	 *       递归调用dfs(x,cur+1);
	 * 	  2.要当前的元素a[cur]
	 *       先将当前元素加入列表(记录合法路径);
	 *       再递归调用dfs(x-a[cur],cur+1);
	 *       将当前元素移出列表(不合法回溯)
	 * 
	 * */
	private static void dfs(int x,int cur) {
		if(x==0) {//出口
			System.out.print("YES ("+k+"=");
			for(int i=0;i<res.size();i++) {//打印
				System.out.print(res.get(i)+(i!=(res.size()-1)?"+":")"));
			}
			System.exit(0);
		}
		if(x<0 || cur==a.length) {
			return;
		}
		//(1)不要当前的元素a[cur]
		dfs(x,cur+1);
		
		//(2)要当前的元素a[cur]
		res.add(a[cur]);//要该元素,加入列表
		int index = res.size()-1;//当前加入元素的下标
	    dfs(x-a[cur],cur+1);
	    res.remove(index);//回溯
	}
	
}



http://www.niftyadmin.cn/n/1023687.html

相关文章

GET请求中URL的最大长度限制总结

由于jsonp跨域请求只能通过get请求&#xff0c;url长度根据浏览器及服务器的不同而有不同限制。 若要支持IE的话&#xff0c;最大的长度为2083字符&#xff0c;若是中文字符的话只有2083/9231个字符。 若是Chrom... 关键字&#xff1a; 服务器,浏览器,url长度限制 今天在写一…

中国的计算机网络技术学校,计算机系网络营销学校,计算机网络技术有哪些专科学校...

全国1、学神中的学神&#xff1a;清华北大2、学神级别&#xff1a;华东五校中科院大学3、学帝级别&#xff1a;北京航空航天大学4、学圣级别&#xff1a;北京邮电大学、华中科技大学5、学霸级别&#xff1a;电子科技大学、华南理工大学6、学师级别&#xff1a;西安电子科技大学…

java bcd 十进制_第十一篇 BCD码调整

无论是X86汇编还是MCS-51的指令集中都会有BCD码调整指令。本博文将浅谈下BCD码调整的相关情况。一、BCD码是十进制数在计算机中的表现形式。我们一直都说计算机只能表示0、1二进制&#xff0c;这毫无疑问是正确的。但人对十进制数较为熟悉&#xff0c;为了迎合人的方便&#xf…

Cocoapods 应用第二部分-私有库相关

我们在这里,使用的是 第一部分使用pod lib create YohunlUtilsPod 创建的framework工程来说明.其创建过程在此就不重复了,当然你也可以下载我已经创建好的demo https://github.com/yohunl/YohunlUtilsPod PS:既然是私有库,那么我们基本上不会使用github的,相信大家公司都有相应…

Jaql 和 Pig 查询语言的比较

基于 MapReduce 框架的大数据量查询语言的选择 简介&#xff1a; 随着信息规模的爆炸式增长&#xff0c;越来越多的公司特别是互联网公司面临着如何利用更效第成本地进行大数据量处理的难题。Google 于 2004 年发表了 MapReduce 编程模型&#xff0c;作为 MapReduce 的开源实现…

java excel模板下载_00006-java 下载一个excel模板(文件),前端layui按钮

下载按钮&#xff1a;模板下载对应方法&#xff1a;downTemplate:function () {window.open(ctx"/download/template/customer");},java 控制层&#xff1a;import org.apache.commons.io.FileUtils;import org.apache.commons.io.IOUtils;import org.slf4j.Logger;i…

7.6 dfs竞赛例题---水洼数(经典题!最后背下!)

import java.util.Scanner;public class Main {/*思路&#xff1a;* &#xff08;1&#xff09;从头开始进行遍历&#xff0c;寻找第一个积水W* &#xff08;1.1&#xff09;从该处进行dfs遍历&#xff0c;* 寻找其8个方向是否有积水W&#xff0c;如果存在将其改为…

win10计算机休眠设置在哪里,win10怎么让屏幕一直亮着 win10设置休眠时间详细教程...

在我们使用电脑时&#xff0c;如果长时间没有操作电脑&#xff0c;在设定的时间到了系统便会自动进入休眠时间&#xff0c;我们要唤醒的话点击一下鼠标即可&#xff0c;有时候我们在使用电脑时需要走开一段时间&#xff0c;但是不想让屏幕休眠&#xff0c;怎么让屏幕一直亮着呢…