摘要：要求中的每一个元素在一个组合中只能被使用一次。输入候选数字集和目标数字结果集应当是想法首先这道题和题非常的相像。因此和题的解法相比，我们需要进行一次对于重复元素跳过的操作。
题目详情
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination. 这道题的意思是，输入一个候选数字集(C)和一个目标数字(T).要求我们找出C中的不同元素组合，使得这些元素加和等于T。要求C中的每一个元素在一个组合中只能被使用一次。
For example, 输入候选数字集 [10, 1, 2, 7, 6, 1, 5] 和目标数字 8,
结果集应当是
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
想法
首先这道题和39题CombinationSum非常的相像。唯一的差别就在于这道题要求，每一个元素只能被使用一次。
因此和39题的解法相比，我们需要进行一次对于重复元素跳过的操作。
解法
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List> res = new ArrayList>();
backtrack(res,new ArrayList(),candidates,target,0);
return res;
}
public void backtrack(List> res,List tempList,int[] candidates,int remain,int start){
if(remain < 0)return;
if(remain == 0){
res.add(new ArrayList<>(tempList));
}else{
for(int i=start;i start && candidates[i] == candidates[i-1]) continue;
tempList.add(candidates[i]);
backtrack(res,tempList,candidates,remain-candidates[i],i+1);
tempList.remove(tempList.size()-1);
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/68526.html
