最后一遍-L40-Combination Sum II
描述：
Given a collection of candidate numbers (candidates) and a target number (target),
find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
Constraints:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
典型的回溯剪枝的写法，借鉴L39
- 如何进行回溯，回溯的开始条件，循环的依据是什么，结束条件是什么？
- 回溯的时候，怎么回，也就是恢复现状？
- 怎么剪枝，就像40题目中的要求没有重复的元素，到底哪些算是重复的数字，对应的剪枝的时候，应该怎么写的
public class L40 {
public static void main(String[] args) {
List<List<Integer>> result = combinationSum2(new int[]{10,1,2,7,6,1,5},8);
for (List tmp : result) {
System.out.println(Arrays.toString(tmp.toArray()));
}
result = combinationSum2(new int[]{2,3,5},8);
for (List tmp : result) {
System.out.println(Arrays.toString(tmp.toArray()));
}
result = combinationSum2(new int[]{2},1);
for (List tmp : result) {
System.out.println(Arrays.toString(tmp.toArray()));
}
}
public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
combinationSum(candidates,target,result,new ArrayList<Integer>(),0);
return result;
}
private static void combinationSum(int[] candidates, int target, List<List<Integer>> result, ArrayList<Integer> sums,int index) {
if(target == 0) {
result.add(new ArrayList<>(sums));
return;
}
for (int i = index; i < candidates.length; i++) {
if (i > index && candidates[i] == candidates[i - 1]) continue;
if(candidates[i] <= target){
sums.add(candidates[i]);
combinationSum(candidates,target-candidates[i],result,sums,i+1);
sums.remove(sums.size()-1);
}
}
}
}