BiruLyu
5/31/2017 - 3:46 AM

## 40. Combination Sum II.java

``````
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){
return;
}
for(int i = start; i < candidates.length; i++){
if( i > start && candidates[i] == candidates[i - 1]) continue;
if(target < candidates[i]) return;