40. Combination Sum II
- Total Accepted: 89506
- Total Submissions: 294097
- Difficulty: Medium
- Contributors: Admin
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.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
Code
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
# no duplication in result. so sort candidates first.
candidates = sorted(candidates)
path, res = [], []
self.dfs(0, candidates, path, res, target)
return res
def dfs(self, start_idx, candidates, path, res, target):
# original target and all candidates are positive
if target < 0:
return
elif target == 0:
res.append(list(path))
return
for i in xrange(start_idx, len(candidates)):
# remove duplication
if i > start_idx and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
self.dfs(i+1, candidates, path, res, target-candidates[i])
path.pop()
Idea
Essentially it is a DFS. In order to avoid duplicate combinations, we sort the candidates first (line 9) and also apply some mechanism at line 25. Then, we try adding `candidates[i]` to path, modifying target to `target-candidates[i]` and recurring on `dfs` method.
Reference: https://discuss.leetcode.com/topic/19845/java-solution-using-dfs-easy-understand