LeetCode#40 Combination Sum II

Problem Definition：

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.
Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
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]

Solution：这题跟上一题的区别在于，待选的元素可能重复出现，但是一个元素不能被多次使用。所以，如果C中有两个1，那在一个解中，最多出现两个1，它们是不同的1。

所以这里要处理重复解的问题，比如上个例子中，实际上有两个潜在的[1,7]，但是最终只能用一个。

可以用HashMap来处理重复（预防多次加入同一种解）saves a lot of time。

 1     # @param {integer[]} candidates
 2     # @param {integer} target
 3     # @return {integer[][]}
 4     def combinationSum2(self, candidates, target):
 5         candidates.sort()
 6         res={}
 7         self.cur(candidates, target, 0, [], res)
 8         return res.values()
 9         
10     def cur(self, nums, target, index, localArr, res):
11         if target==0:
12             key=str(localArr)
13             if key not in res:
14                 res[key]=localArr[:]
15         else:
16             for i in range(index, len(nums)):
17                 nt=target-nums[i]
18                 if nt>=0:
19                     localArr.append(nums[i])
20                     self.cur(nums, nt, i+1, localArr, res)
21                     localArr.pop()
22                 else:
23                     break