class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort();
res = [];
self.backtracking(candidates, target, 0, [], res)
return res;
def backtracking(self, candidates, target, start, temp, res):
if target == 0:
return res.append(temp);
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue;
if target < candidates[i]:
return;
self.backtracking(candidates, target - candidates[i], i + 1, temp + [candidates[i]], res);
# Each number in candidates can be used only once, thus update start = i + 1;
"""
TESTCASES:
Input:
[10,1,2,7,6,1,5]
8
Output:
[[1,1,6],[1,2,5],[1,7],[2,6]]
"""
public class Solution {
public void backtracking(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> res){
if(target == 0){
res.add(new ArrayList(temp));
return;
}
for(int i = start; i < candidates.length; i++){
if( i > start && candidates[i] == candidates[i - 1]) continue;
if(target < candidates[i]) return;
temp.add(candidates[i]);
backtracking(candidates, target - candidates[i], i + 1, temp, res);
temp.remove(temp.size()-1);
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<List<Integer>>();
backtracking(candidates, target, 0, new ArrayList<Integer>(), res);
return res;
}
}