1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Combination Sum II
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/combination-sum-ii/
7+ Notes:
8+ Given a collection of candidate numbers (C) and a target number (T), find all unique combinations
9+ in C where the candidate numbers sums to T.
10+ Each number in C may only be used once in the combination.
11+ Note:
12+ All numbers (including target) will be positive integers.
13+ Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
14+ The solution set must not contain duplicate combinations.
15+ For example, given candidate set 10,1,2,7,6,1,5 and target 8,
16+ A solution set is:
17+ [1, 7]
18+ [1, 2, 5]
19+ [2, 6]
20+ [1, 1, 6]
21+
22+ Solution: ..Similar to Combination Sum I, except for line 42 && 44.
23+ */
24+ public class Solution {
25+ public List <List <Integer >>combinationSum2 (int []num ,int target ) {
26+ List <List <Integer >>res =new ArrayList <List <Integer >>();
27+ Arrays .sort (num );
28+ ArrayList <Integer >path =new ArrayList <Integer >();
29+ combinationSumRe (num ,target ,0 ,path ,res );
30+ return res ;
31+ }
32+ void combinationSumRe (int []candidates ,int target ,int start ,ArrayList <Integer >path ,List <List <Integer >>res ) {
33+ if (target ==0 ) {
34+ ArrayList <Integer >p =new ArrayList <Integer >(path );
35+ res .add (p );
36+ return ;
37+ }
38+ for (int i =start ;i <candidates .length &&target >=candidates [i ]; ++i ) {
39+ if (i !=start &&candidates [i -1 ] ==candidates [i ])continue ;
40+ path .add (candidates [i ]);
41+ combinationSumRe (candidates ,target -candidates [i ],i +1 ,path ,res );
42+ path .remove (path .size () -1 );
43+ }
44+ }
45+ }
