【题目】
“给定一个整数数组和一个目标数S，如何输出该数组中所有和为S的可能组合？”，你会如何做呢？
例如，给定数组 如下：
代码语言：javascript复制int[] values = { 1, 3, 4, 5, 6, 15 };那么和为15的可能组合有如下几种：
代码语言：javascript复制15 = 1 3 5 6
15 = 4 5 6
15 = 15****************下面有解法，请先自我思考 *******************
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
【解法】
针对该问题，解决的方法有很多种。在这篇文章中，我将为大家给出两种解决方法：一个是“借助Stack实现”；另外一个是“不借助Stack实现”。
方法一：借助Stack实现
代码语言：javascript复制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());
}
}测试一下：
代码语言：javascript复制/**
*
* @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实现
代码语言：javascript复制/**
* @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());
}
}测试一下：
代码语言：javascript复制/**
*
* @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
