改了挺多次，不过最后还是被我搞出来了^^, 用了map的技巧勉强过了large。
1 class Solution { 2 public: 3 void dfs(vector<int> num, int target, int sum, vector<int> &save, map<vector<int>, int> &reti, int cur) { 4 if (sum > target) return; 5 if (sum == target) { 6 reti.insert(pair<vector<int>, int>(save, 0)); 7 return; 8 } 9 for (int i = cur; i < num.size(); i++) { 10 save.push_back(num[i]); 11 dfs(num, target, sum+num[i], save, reti, i+1); 12 save.pop_back(); 13 } 14 } 15 vector<vector<int> > combinationSum2(vector<int> &num, int target) { 16 // Start typing your C/C++ solution below 17 // DO NOT write int main() function 18 vector<vector<int>> ret; 19 map<vector<int>, int> reti; 20 if (num.size() == 0) return ret; 21 sort(num.begin(), num.end()); 22 vector<int> save; 23 int sum = 0; 24 int cur = 0; 25 dfs(num, target, sum, save, reti, cur); 26 for (map<vector<int>, int>::iterator it = reti.begin(); it != reti.end(); it++) { 27 ret.push_back(it->first); 28 } 29 return ret; 30 } 31 };
C#
1 public class Solution { 2 public List<List<int>> CombinationSum2(int[] candidates, int target) { 3 Array.Sort(candidates); 4 int sum = 0; 5 List<List<int>> ans = new List<List<int>>(); 6 List<int> tmp = new List<int>(); 7 if (candidates.Length == 0) return ans; 8 int dep = 0; 9 dfs(candidates, target, sum, ref tmp, ref ans, dep); 10 return ans; 11 } 12 void dfs(int[] candidates, int target, int sum, ref List<int> tmp, ref List<List<int>> ans, int dep) 13 { 14 if (sum > target) return; 15 if (sum == target) { 16 List<int> newTmp = new List<int>(); 17 for (int i = 0; i < tmp.Count; i++) newTmp.Add(tmp[i]); 18 ans.Add(newTmp); 19 return; 20 } 21 for (int i = dep; i < candidates.Length; i++) { 22 if (i > dep && candidates[i] == candidates[i-1]) continue; 23 tmp.Add(candidates[i]); 24 dfs(candidates, target, sum + candidates[i], ref tmp, ref ans, i+1); 25 tmp.RemoveAt(tmp.Count - 1); 26 } 27 } 28 }