给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
分析:
这个的难点在于,每个数字在每个组合中只能使用一次,注意,这不是在说 每个组合的数字只能使用一次 也不是在说 每个组合的数字不能重复,这就很绕,但是既然牵扯到重复数字,那么开始时一定要对数组进行排序
同时,对于数组中的元素是否被使用,本题中引入了一个很常用的概念,即boolean数组flag,用来标记是否被使用
参考代码:
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
boolean[] flag = new boolean[candidates.length];
sup(candidates,target,0,flag);
return ret;
}
List>ret = new ArrayList<>();
LinkedList
private void sup(int[] candidates,int target,int index,boolean[] flag){
if(target<0) return;
if(target==0){
ret.add(new ArrayList<>(path));
return;
}
for(int i=index;i
if(i>0&&candidates[i]==candidates[i-1]&&!flag[i-1]) continue;
flag[i]=true;
path.add(candidates[i]);
target-=candidates[i];
sup(candidates,target,i+1,flag);
target+=candidates[i];
path.removeLast();
flag[i]=false;
}
}
