首页 > 代码库 > 【leetcode】Subsets II (middle) ☆
【leetcode】Subsets II (middle) ☆
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], []]
思路：回溯法是肯定的了，我用的深度优先，先把输入的S排序，这样当考虑了前面的数字后，后面的讨论中就不需要再考虑该数字了。需要对每次的子序列判断是否已经重复出现。
代码AC了，但是800ms太慢，贴边过的。
class Solution {public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int>> ans; vector<int> null; ans.push_back(null); if(S.size() == 0) return ans; sort(S.begin(), S.end()); DFS(ans, S); return ans; } void DFS(vector<vector<int>> &ans, vector<int> S) { if(S.empty()) return; vector<int> vPreLen = ans.back(); while(!S.empty()) { vector<int> v = vPreLen; int cur = S[0]; v.push_back(cur); S.erase(S.begin()); if(!isalreadyhave(ans, v)) { ans.push_back(v); DFS(ans, S); } } return; } bool isalreadyhave(vector<vector<int>> ans, vector<int> v) { for(int i = 0; i < ans.size(); i++) { if(v == ans[i]) return true; } return false; }};
大神的思路：48ms
在压入答案的时候就保证不会重复，把重复的部分如（5,5,5）看做一个特殊的数，压入时可以压入1个、2个、3个。
把S排序后，按顺序从第一个到最后一个得到该数字加入后，可以得到的新的子序列。每次加入一个新的数字后，新的数字会使得所有之前已经压入的子序列产生新的子序列。
class Solution {public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > totalset = {{}}; sort(S.begin(),S.end()); for(int i=0; i<S.size();){ int count = 0; // num of elements are the same while(count + i<S.size() && S[count+i]==S[i]) count++; int previousN = totalset.size(); for(int k=0; k<previousN; k++){ vector<int> instance = totalset[k]; for(int j=0; j<count; j++){ instance.push_back(S[i]); totalset.push_back(instance); } } i += count; } return totalset; }};
【leetcode】Subsets II (middle) ☆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。