Given a collection of integers that might contain duplicates, S, return all possible subsets. [ 1 public static List<List<int>> SubsetsII2(List<int> S) 2 { 3 S.Sort(); 4 List<List<int>> ret = new List<List<int>>(); 5 6 List<int> empty = new List<int>(); 7 ret.Add(empty); 8 9 int start = 0; 10 for (int i = 0; i < S.Count; i++) 11 { 12 int prev_count = ret.Count; 13 for (int j = start; j < prev_count; j++) 14 { 15 List<int> temp = new List<int>(ret[j]); 16 temp.Add(S[i]); 17 ret.Add(temp); 18 } 19 20 if ((i < S.Count - 1) && (S[i + 1] == S[i])) 21 start = prev_count; 22 else 23 start = 0; 24 } 25 26 return ret; 27 } 代码分析: 比Subsets那题多一个start变量,如果后一个元素跟当天这个相同,下次loop前面的时候就不要从头开始,从prev_count(上一次开始插入的位置)开始。当然也有递归的做法,不贴了。Combinatoric的做法就不适合。 |
|
来自: 雪柳花明 > 《LeetCode》