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], [] ]
class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > ret; if(S.size() == 0) return ret; sort(S.begin(), S.end()); vector<int> tmp; dfs(S, 0, tmp, ret); return ret; } void dfs(vector<int> &S, int beg, vector<int> tmp, vector<vector<int> > &ret) { ret.push_back(tmp); if(beg >= S.size()) return; for(int i = beg; i < S.size(); ++i) { if(i == beg || S[i] != S[i-1]) { tmp.push_back(S[i]); dfs(S, i+1, tmp, ret); tmp.pop_back(); } } } };
欢迎关注微信公众号——计算机视觉:
相关推荐
15. 在处理包含重复元素的问题时,如Subsets II,需要考虑如何避免生成重复的子集。 16. 动态规划(DP)和深度优先搜索(DFS)是解决算法问题的两种常用方法。动态规划可以用来解决0-1背包问题,而DFS则可以用于...
10. **Subsets II .cpp** - 第90题“子集II”,要求找到一个集合的所有不重复子集,解冑通常使用递归或回溯法。 以上代码覆盖了算法设计中的多种重要思想,包括回溯法、动态规划、字符串处理、区间操作和深度/广度...
题目描述的是一个经典的编程问题,来源于LeetCode上的"子集II"(Subsets II,编号为101)题目。该问题要求找到一个整数数组中所有不含有重复元素的子集(幂集),并确保结果中不包含重复的子集。 在给定的代码中,...
C++实现时那个返回值是void也着实让我困惑了好久 Subsets DFS实现,竟然还WA了好几次。 Climbing Stairs 入门级记忆化dp 2014.10.30 Merge Sorted Array 归并排序基础 Remove Duplicates from Sorted List 脑残简单...
- **Basic Calculator II**:实现一个基本计算器,读取一个表达式并返回计算结果。 本书通过实际编程案例,讲解了各种算法思想和技巧,涵盖了从基础的数据结构(如数组、链表、树)到复杂的问题解决策略(如动态...
5.1 Generating subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Generating permutations . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3 Backtracking . . . . . . . . . ...