LeetCode --- 40. Combination Sum II

タイトルリンク:Combination Sum II
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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
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] 

この問題の要求は,候補数Cとターゲット数Tのセットを与え,すべてのCにおける数字の組合せを見つけてTとすることである.数字は1回しか選択できません.
備考:すべての候補数は正数で、数値の組合せを非減算で返すには、重複要素は含まれません.
この問題はCombination Sumとあまり差がなく、同じようにすべての状況を返すことを要求し、同じNP問題であり、遡及方式を通じて、すべての状況を一つ一つ見つけることができる.
違いは、この問題の候補数字には重複数字が含まれており、数字ごとに1回しか選択できないことだ.したがって、再帰処理では、いくつかの詳細が異なります.
現在の候補数が前の候補数に等しいか否かを判断する判定コードを追加する必要がある.
再帰する場合は、現在の候補数ではなく、次の候補数から開始する必要があります.
時間複雑度:O(??)
空間複雑度:O(nm)(結果数)

 1 class Solution
 2 {
 3     vector<vector<int> > vvi;
 4 public:
 5     vector<vector<int> > combinationSum2(vector<int> &num, int target)
 6     {
 7         sort(num.begin(), num.end());
 8         
 9         vector<int> vi;
10         combinationSum2(num, target, 0, vi);
11         return vvi;
12     }
13 
14 private:
15     void combinationSum2(vector<int> &num, int target, int i, vector<int> &vi)
16     {
17         if(target == 0)
18         {
19             vvi.push_back(vi);
20             return;
21         }
22 
23         for(int j = i; j < num.size(); ++ j)
24         {
25             if(target < num[j])
26                 break;
27             
28             if(j > i && num[j] == num[j - 1])
29                 continue;
30 
31             vi.push_back(num[j]);
32             combinationSum2(num, target - num[j], j + 1, vi);
33             vi.pop_back();
34         }
35     }
36 };

転載は出典:LeetCode---40.Combination Sum II