class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//创建结果数组
List<List<Integer>> ans = new ArrayList<>();
if(candidates.length == 0 || target == 0){
return ans;
}
//不重复问题一般先排序
Arrays.sort(candidates);
//调用回溯方法
backtrack(0,candidates,target,new ArrayList<>(),ans);
return ans;
}
//回溯方法
public void backtrack(int start,int[] candidates,int target,ArrayList<Integer> track,List<List<Integer>> ans){
if(target < 0){
return;
}
//满足条件
if(target == 0){
ans.add(new ArrayList<>(track));
}
//选择列表
for(int i = start;i <candidates.length;i++){
//做选择
if(i > start && candidates[i] == candidates[i-1]){
continue;
}
track.add(candidates[i]);
//回溯
backtrack(i+1,candidates,target-candidates[i],track,ans);
//撤销选择
track.remove(track.size()-1);
}
}
}
