输出给定数组中所有和为S的可能组合
如果给定一个整数数组和一个目标数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
原文地址:https://my.oschina.net/wangmengjun/blog/775973
相关推荐
-
go Panic & Recover Java基础
2020-6-16
-
关于Java面试,你应该准备这些知识点 Java基础
2018-3-18
-
AbstractQueuedSynchronizer 原理分析 – Condition 实现原理 Java基础
2019-3-22
-
不要再问我Java程序是怎么执行的了! Java基础
2019-7-28
-
Java并发编程之ReentrantLock源码分析 Java基础
2020-5-30
-
Android、iPhone和Java三个平台一致的加密工具 Java基础
2019-9-9
-
花了几个小时总结了一些容易出错的 Java 知识点! Java基础
2020-6-20
-
对于Ping的过程,你真的了解吗? Java基础
2020-5-30
-
深入理解Java字符集编码和解码 Java基础
2019-11-2
-
图解十大经典排序算法(Java版本) Java基础
2020-6-15