文档章节

输出给定数组中所有和为S的可能组合

王孟君
 王孟君
发布于 2016/10/26 14:42
字数 829
阅读 256
收藏 9

如果给定一个整数数组和一个目标数S,如何输出该数组中所有和为S的可能组合?

例如,

给定数组 如下:

int[] values = { 1, 3, 4, 5, 6, 15 };

那么和为15的可能组合有如下几种:

15 = 1+3+5+6
15 = 4+5+6
15 = 15

本文采用如下两种方法来实现:

  • 借助Stack实现
  • 不借助Stack实现

借助Stack实现

代码实现

import java.util.Arrays;
import java.util.Stack;

/**
 * 
 * @author wangmengjun
 *
 */
public class PrintAllByStack {

	/** 设定一个目标值 */
	public static final int TARGET_SUM = 20;

	/** 使用Stack存放已经使用的数值 */
	private Stack<Integer> stack = new Stack<Integer>();

	/** 存放当前Stack中元素的和 */
	private int sumInStack = 0;

	public void process(final int[] data, int target) {
		if (data == null || data.length == 0) {
			throw new IllegalArgumentException("data不能为空");
		}

		Arrays.sort(data);
		processRecursion(data, 0, data.length, target);
	}

	private void processRecursion(final int[] data, int fromIndex,
			int endIndex, int target) {

		if (sumInStack >= target) {
			if (sumInStack == target) {
				print(stack);
			}
			return;
		}

		for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
			if (sumInStack + data[currentIndex] <= target) {
				stack.push(data[currentIndex]);
				sumInStack += data[currentIndex];
				/**
				 * 从currentIndex +1开始继续递归
				 */
				processRecursion(data, currentIndex + 1, endIndex, target);
				sumInStack -= (Integer) stack.pop();
			}
		}
	}

	/**
	 * 打印符合条件的结果,如 15 = 4+6+5
	 */
	private void print(Stack<Integer> stack) {
		StringBuilder sb = new StringBuilder();
		sb.append(TARGET_SUM).append(" = ");
		for (Integer i : stack) {
			sb.append(i).append("+");
		}
		System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
	}
}

测试及结果

/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

	public static void main(String[] args) {
		PrintAllByStack example = new PrintAllByStack();
		int[] values = { 1, 4, 3, 6, 7, 9, 5, 8, 15, 16, 18, 17 };
		example.process(values, PrintAllByStack.TARGET_SUM);
	}

}

 

20 = 1+3+4+5+7
20 = 1+3+7+9
20 = 1+3+16
20 = 1+4+6+9
20 = 1+4+7+8
20 = 1+4+15
20 = 1+5+6+8
20 = 3+4+5+8
20 = 3+4+6+7
20 = 3+8+9
20 = 3+17
20 = 4+7+9
20 = 4+16
20 = 5+6+9
20 = 5+7+8
20 = 5+15

 

在上述代码中,Stack作为辅助,在递归方法外定义, 这样有点奇怪

接下来的方法,我们将Stack替换掉。

不借助Stack实现

代码

测试及结果

/**
 * @author wangmengjun
 *
 */
import java.util.Arrays;

public class PrintAllSubsets {

	/** 设定一个目标值 */
	public static final int TARGET_SUM = 20;

	public void process(final int[] data, final int target) {
		if (data == null || data.length == 0) {
			throw new IllegalArgumentException("data不能为空");
		}

		int len = data.length;
		/**
		 * 处理前先排序一下,这样有一个好处,如果一个数添加进去已经大于target了,
		 * 那么该数后面的数添加进去都将大于target
		 */
		Arrays.sort(data);
		this.processRecursion(data, 0, new int[len], 0, target);
	}

	private void processRecursion(final int[] data, int fromIndex,
			final int[] stack, final int stacklen, final int target) {
		if (target == 0) {
			/**
			 * 如果符合条件,则输出符合条件的情况
			 */
			printResult(Arrays.copyOf(stack, stacklen));
			return;
		}
		
		while (fromIndex < data.length && data[fromIndex] > target) {
			/**
			 * 借助数组已经排序的好处,后面更大的数值,只要增加索引即可。
			 */
			fromIndex++;
		}

		while (fromIndex < data.length && data[fromIndex] <= target) {
			/**
			 * 当数据用完,或者当数值大于剩余想获取的目标值,结束循环
			 */
			stack[stacklen] = data[fromIndex];
			processRecursion(data, fromIndex + 1, stack, stacklen + 1, target
					- data[fromIndex]);
			fromIndex++;
		}
	}

	/**
	 * 打印符合条件的结果,如 15 = 4+6+5
	 */
	private void printResult(int[] copyOf) {
		StringBuilder sb = new StringBuilder();
		sb.append(TARGET_SUM).append(" = ");
		for (Integer i : copyOf) {
			sb.append(i).append("+");
		}
		System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
	}
}

测试及结果


/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

	public static void main(String[] args) {
		PrintAllSubsets example = new PrintAllSubsets();
		int[] values = { 1, 4, 3, 6, 7, 9, 5, 8, 15, 16, 18, 17 };
		example.process(values, PrintAllSubsets.TARGET_SUM);
	}

}
20 = 1+3+4+5+7
20 = 1+3+7+9
20 = 1+3+16
20 = 1+4+6+9
20 = 1+4+7+8
20 = 1+4+15
20 = 1+5+6+8
20 = 3+4+5+8
20 = 3+4+6+7
20 = 3+8+9
20 = 3+17
20 = 4+7+9
20 = 4+16
20 = 5+6+9
20 = 5+7+8
20 = 5+15

 

© 著作权归作者所有

王孟君

王孟君

粉丝 226
博文 94
码字总数 221044
作品 0
杭州
高级程序员
私信 提问
某公司的笔试编程题

原题:     给定一个数组candidate和一个目标值target,求出candidate中两个数的和等于target的组合。比如输入数组[1,2,3,4,7]和目标值10.输出[ 3, 7]如果找不到输出[ -1,-1 ]。要求时间复...

装置图
2016/09/26
0
0
LeetCode算法题-Letter Case Permutation(Java实现)

这是悦乐书的第315次更新,第336篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第184题(顺位题号是784)。给定一个字符串S,将每个字母单独转换为小写或大写以创建另一个字符...

小川94
04/24
0
0
递归算法之排列组合-求一个集合S的m个元素的组合和所有可能的组合情况

  求一个集合S的m个元素组合的所有情况,并打印出来,非常适合采用递归的思路进行求解。因为集合的公式,本身就是递归推导的: C(n,m) = C(n-1,m-1) + C(n-1,m)。   根据该公式,每次递归...

Burkut
05/07
0
0
【NCRE二级C语言】105套题答案

NCRE等级考试秘笈 第一套 填空: 给定程序的功能是调用fun函数建立班级通讯录。通讯录中记录每名学生的编号、姓名和电话号码。班级的人数和学生的信息从键盘读入,每个人的信息作为一个数据块...

Debug客栈
03/15
0
0
【精选】JAVA入门算法题(六)

版权声明:很高兴认识你,我叫邵龙飞 原创文章,转载请注明 https://blog.csdn.net/qq_37482202/article/details/84928701 不只为了糊口,还要有抱负。你要想:在这个行业中,我要成为什幺样的...

幽蓝丶流月
2018/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

jQuery使用GET方式来进行异步请求

jQuery.get( url, [data], [callback] ):使用GET方式来进行异步请求 参数: url(String) : 发送请求的URL地址. data(Map) : (可选) 要发送给服务器的数据,以 Key/value 的键值对形式表示,...

前端老手
7分钟前
2
0
网络安全市场需求

最近,网络安全技能差距的热门话题流传开来。技能差距经常被紧急讨论,可以看出它在实践中的作用是很大的。但信息安全是一门广泛的学科,所以在谈论“技能差距”时需要更具体。有专家表示,真...

linuxCool
24分钟前
3
0
定期批量改密,实现高效运维,保障口令安全

随着企业IT资产规模的不断增大,各类主机、应用系统的管理也变得愈加困难。 对于系统管理员来说,保证操作系统的密码安全是其重要工作,在需要维护众多的主机时,其面临的困境将是: 1、难以...

堡垒啊
49分钟前
5
0
怎样在磁盘上查找MySQL表的大小?这里有答案

导读 我想知道 MySQL 表在磁盘上占用多少空间,但看起来很琐碎。不应该在 INFORMATION_SCHEMA.TABLES 中提供这些信息吗?没那么简单! 我想知道 MySQL 表在磁盘上占用多少空间,但看起来很琐碎...

问题终结者
今天
6
0
Spring Boot缓存实战 Redis 设置有效时间和自动刷新缓存-2

问题 上一篇Spring Boot Cache + redis 设置有效时间和自动刷新缓存,时间支持在配置文件中配置,说了一种时间方式,直接扩展注解的Value值,如: @Override@Cacheable(value = "people#${s...

xiaolyuh
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部