本文将记录实现“从一个整数数组中找出总和为S的所有子集”功能的两种方法。
1. 使用Stack来实现
2. 不借助Stack来实现。
使用Stack来实现
import java.util.Stack;
public class GetAllSubsetByStack {
/** Set a value for target sum */
public static final int TARGET_SUM = 15;
private Stack<Integer> stack = new Stack<Integer>();
/** Store the sum of current elements stored in stack */
private int sumInStack = 0;
public void populateSubset(final int[] data, int fromIndex, int endIndex) {
if (sumInStack >= TARGET_SUM) {
if (sumInStack == TARGET_SUM) {
print(stack);
}
// there is no need to continue when we have an answer
// because nothing we add from here on in will make it
// add to anything less than what we have...
return;
}
for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
if (sumInStack + data[currentIndex] <= TARGET_SUM) {
stack.push(data[currentIndex]);
sumInStack += data[currentIndex];
/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
populateSubset(data, currentIndex + 1, endIndex);
sumInStack -= (Integer) stack.pop();
}
}
}
/**
* Print satisfied result. i.e. 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());
}
}
方法调用的类:
public class Main {
private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
14, 15 };
public static void main(String[] args) {
GetAllSubsetByStack example = new GetAllSubsetByStack();
example.populateSubset(DATA, 0, DATA.length);
}
}
不借助Stack来实现
import java.util.Arrays;
public class GetAllSubsets {
/** Set a value for target sum */
public static final int TARGET_SUM = 15;
public void populateSubset(final int[] data, int fromIndex,
final int[] stack, final int stacklen, final int target) {
if (target == 0) {
// exact match of our target. Success!
printResult(Arrays.copyOf(stack, stacklen));
return;
}
while (fromIndex < data.length && data[fromIndex] > target) {
// take advantage of sorted data.
// we can skip all values that are too large.
fromIndex++;
}
while (fromIndex < data.length && data[fromIndex] <= target) {
// stop looping when we run out of data, or when we overflow our
// target.
stack[stacklen] = data[fromIndex];
populateSubset(data, fromIndex + 1, stack, stacklen + 1, target
- data[fromIndex]);
fromIndex++;
}
}
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());
}
}
方法调用的类:
public class Main {
private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
14, 15 };
public static void main(String[] args) {
GetAllSubsets example = new GetAllSubsets();
example.populateSubset(DATA, 0, new int[DATA.length], 0, 15);
}
}
两种实现方法都会打印出如下的结果:
15 = 1+3+4+5+2
15 = 1+3+4+7
15 = 1+3+5+6
15 = 1+3+2+9
15 = 1+3+11
15 = 1+4+2+8
15 = 1+4+10
15 = 1+5+2+7
15 = 1+5+9
15 = 1+6+8
15 = 1+14
15 = 3+4+6+2
15 = 3+4+8
15 = 3+5+7
15 = 3+2+10
15 = 4+5+6
15 = 4+2+9
15 = 4+11
15 = 5+2+8
15 = 5+10
15 = 6+2+7
15 = 6+9
15 = 2+13
15 = 7+8
15 = 15
转载请注明出处:
http://mouselearnjava.iteye.com/blog/1985360
分享到:
相关推荐
# 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 # 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 # 示例 1: # 输入:nums = [1,2,3] # 输出:[[],[1],[2],[1...
对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,编程计算S 的一个子集 S1,使得x∈S1,∑x=c. Input 由文件input.txt 提供输入数据。文件第1 行有2 个正整数n 和c,n 表示S 的大小,c 是子集和的目标值。接...
给定一个整数集合X={x[1],x[2],……,x[n]}和整数y,找出和等于y的X的子集Y
子集和问题的一个实例为〈S,c〉。其中,S={x1,x2,…,xn}是一个正整数的集合,c是一个正整数。子集和问题判定是否存在S的一个子集S1,使得 ∑x=c, (其中x∈S1)。试设计一个解子集和问题的方法。你可以假设处理范围...
输出n个字符(不限整数)的所有子集 C++ 数据结构 实验一
算法设计:对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,计算S的一个子集S1,使得子集里的元素之和为c。 数据输入:由文件input.txt提供输入数据。文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值...
对于给定的正整数的集合 S={x1,x2,…,xn }S={x1,x2,…,xn }和正整数 c,编程计算 S 的一个子集S1,使得∑x∈S1x=c ∑x∈S1x=c。数据输入:第 1 行有 2 个正整数 n 和 c,n 表示 S 的大小,c是子集和的目标值。...
子集和问题的一个实例为〈S,t〉。其中,S={ 1 x , 2 x ,…, n x }是一个正整数的集合,c是一个正整数。子集和问题判定是否存在S的一个子集S1,使得 S1中的所有元素之和等于c。
给定一个整数n,求出所有连续的且和为n正整数。比如对于整数27,结果为2~7、8~10、13和14,因为这些数之间的整数的和都是27。注意:并不是所有的整数都有结果,例如不存在连续的整数和为16。为了提高计算的效率,...
有1个包含N个整数的数组A,定义1个数组的美丽值为数组中所有不同整数的和。求数组A的所有连续子序列的美丽值之和。
给定一个n个整数的集合X={x1,x2....xn}和整数y,找出和等于y的X的子集Y.
试写一个递归算法实现求一个集合的所有子集。 算法设计: 给定一个非空的集合,用递归算法输出它的所有子集。 数据输入: 由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素...
已知N个大于0的整数构成一个集合,即{1,2,3,……,N},求其所有的非空且元素不相邻的子集,计算所有子集的乘积的平方的和。
Get subset of integers in a file named "source" ,which is in the same directory 即 求一个整数集合的子集,集合元素的个数不限, 采用读取文件的方式
要求将A划分成互不相交的子集A1,A2,……Ak,(k≤n),使任何子集中的元素均无冲突关系,同时要求分子集个数尽可能少 例A={1,2,3,4,5,6,7,8,9} R={ (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7...
设计和实现子集合问题,使用的编程语言是java