问题描述
给定一个无重复元素、且只包含正整数的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);
}
}
}
领取专属 10元无门槛券
私享最新 技术干货