数字组合之和等于目标数

问题描述

给定一个无重复元素、且只包含正整数的int数组candidates，以及一个目标数target，然后，需要你在candidates中寻找一些数字组合起来，让它们的和等于target，你得求出所有这样的组合。注意，candidates中每个元素可以重复选取，但结果集中不能有重复的组合。例如

输入: candidates=[2,3,6], target=8

输出: [[2,2,2,2], [2,3,3], [2,6]]

问题分析

这个问题，是多步骤决策求所有解，适合用回溯法求解，回溯就会用到递归。递归当前这一层需要做的事情是，选取一个元素，加入到临时列表temp，由于每个元素都有被选取的可能，所以，外边有个for循环，穷举所有元素，但这里我们可以做个优化，初始化时，对candidates作个排序，这样当target小于当前的选取的元素时，candidates后面的元素就都不用考虑了。for循环里边，选取一个元素后，那么target-candidates[i]就作为下一层递归的target，每一层递归的最开始的几行代码，用来判断target是否等于0，等于0，意味着已经找到了该问题的一个解，可以将temp加入到result列表中，这里需要注意的是，要用

result.add (new LinkedList(temp));

相当于将当前的temp深度复制了一份，

而不能用 result.add (temp);

因为temp里边的内容是一直在变化的。

递归里边还携带了一个start参数，用于初始化for循环的i，这样可以保证每层循环都只能从后面不断选取数字，而不能选前面的，避免结果集中出现重复的组合。

代码实现

@Test

public void testCombination() {

int[] candidates = new int[]{2, 3, 4, 6};

Solution solution = new Solution();

System.out.println("result :" +

solution.generateSum(candidates, 8));

}

private class Solution {

List result = new LinkedList();

public List generateSum(

int[] candidates, int target) {

result.clear();

if (candidates == null || candidates.length == 0) {

return result;

}

Arrays.sort (candidates);

generate(candidates, 0, new LinkedList(),

target);

return result;

}

public void generate (int[] candidates, int start,

List temp, int target) {

if (target == 0) {

result.add (new LinkedList(temp));

return;

}

for (int i = start; i < candidates.length

&& candidates[i]

temp.add (candidates[i]);

System.out.println("enter: i= " + i

+", temp= "+temp+", target= "+target);

generate (candidates, i, temp,

target - candidates[i]);

temp.remove (temp.size() - 1);

System.out.println("back: i= " + i

+", temp= "+temp+", target= "+target);

}

}

}