文档章节

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

王孟君
 王孟君
发布于 2016/10/26 14:42
字数 829
阅读 199
收藏 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

 

© 著作权归作者所有

王孟君

王孟君

粉丝 227
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

Python猫荐书系列之七:Python入门书籍有哪些?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/ArN-6mLPzPT8Zoq0Na_tsg 最近,猫哥的 Python 技术学习群里进来了几位比较特殊的同学:一...

豌豆花下猫
20分钟前
0
0
一、容器(Containers)

在容器模型中,容器大致类似于VM。他们的主要不同之处在于,每个容器不需要自己完整的操作系统。事实上,所有单个主机上的容器共享整个操作系统。这就释放了大量的系统资源,如CPU、RAM和存储...

倪伟伟
29分钟前
1
0
Guava RateLimiter限流源码解析和实例应用

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流 缓存 缓存的目的是提升系统访问速度和增大系统处理容量 降级 降级是当服务出现问题或者影响到核心流程时,需要暂时屏蔽掉,待高...

算法之名
32分钟前
5
0
国产达梦数据库与MySQL的区别

背景 由于项目上的需要,把项目实现国产化,把底层的MySQL数据库替换为国产的达梦数据库,花了一周的时间研究了国产的数据库-达梦数据库,它和MySQL有一定的区别,SQL的写法也有一些区别。 ...

TSMYK
42分钟前
0
0
老也有错?35岁程序员是一道坎,横亘在每个技术职场人的心中

随着互联网的高速发展变革,大龄恐惧症越来越多地在技术圈被人讨论。很多程序员在工作5-10年以后,都会开始思考5年、10年甚至更久以后的自己,会是怎样一种生活工作状态,以及是否会被时代抛...

我最喜欢三大框架
47分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部