题目描述
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。
解题思路
if(i
> start
&& nums
[i
] == nums
[i
- 1]) continue;
代码
class Solution {
public List
<List
<Integer>> combinationSum2(int[] candidates
, int target
) {
List
<List
<Integer>> list
= new ArrayList<>();
Arrays
.sort(candidates
);
backtrack(list
, new ArrayList<>(), candidates
, target
, 0);
return list
;
}
private void backtrack(List
<List
<Integer>> list
, List
<Integer> tempList
, int[] nums
, int remian
, int start
){
if(remian
< 0) return;
else if(remian
== 0) list
.add(new ArrayList<>(tempList
));
else{
for(int i
= start
; i
< nums
.length
; i
++){
if(i
> start
&& nums
[i
] == nums
[i
- 1]) continue;
tempList
.add(nums
[i
]);
backtrack(list
, tempList
, nums
, remian
- nums
[i
], i
+ 1);
tempList
.remove(tempList
.size() - 1);
}
}
}
}
参考：https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
