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

王孟君

``int[] values = { 1, 3, 4, 5, 6, 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实现

### 代码

``````/**
* @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
``````

### 王孟君

2016/09/26
0
0
LeetCode算法题-Letter Case Permutation（Java实现）

04/24
0
0

求一个集合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入门算法题（六）

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

49分钟前
5
0

6
0
Spring Boot缓存实战 Redis 设置有效时间和自动刷新缓存-2

xiaolyuh

14
0