SubsetsII [source code]
public class SubsetsII {
static
/******************************************************************************/
class Solution {
String indent = "";
boolean DEBUG = false;
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort (nums);
List<List<Integer>> res = new ArrayList<> ();
search (nums, 0, new ArrayDeque<> (), res, new boolean[nums.length]);
return res;
}
void search (int[] nums, int pos, Deque<Integer> path, List<List<Integer>> lss, boolean[] used) {
String old_indent = indent, header = "";
if (DEBUG) header = String.format ("pos:(%d), path:%s, lss:%s, used:%s\n", pos, path, lss, Arrays.deepToString (new boolean[][] {used}));
if (DEBUG) indent += " ";
if (DEBUG) System.out.printf ("%s%s", indent, header);
if (pos == nums.length) {
lss.add (new ArrayList<> (path));
return;
}
if (!(pos > 0 && nums[pos] == nums[pos - 1] && !used[pos - 1])) {
used[pos] = true;
path.push (nums[pos]);
search (nums, pos + 1, path, lss, used);
path.pop ();
used[pos] = false;
}
search (nums, pos + 1, path, lss, used);
indent = old_indent;
}
}
/******************************************************************************/
public static void main(String[] args) {
SubsetsII.Solution tester = new SubsetsII.Solution();
int k = 2;
int[][][] inputs = {
{{1,2,2}}, {{},{1},{1,2},{1,2,2},{2},{2,2}},
};
for (int i = 0; i < inputs.length / k; i++) {
int[] nums = inputs[k * i][0];
int[][] ans = inputs[k * i + 1];
System.out.println (Printer.separator ());
List<List<Integer>> output = tester.subsetsWithDup (nums);
System.out.printf ("[%s] -> %s, expected: %s\n",
Printer.array (nums), output, Arrays.deepToString (ans)
);
}
}
}
sort去重
想要先sort, 尤其是有duplicate的时候, 有些时候sort甚至是去重的必不可少的手段;
类似前面几个排列组合题目的思路, 想要去重, 首先搞清楚, under what circumstances will there be duplicates; 找到这个的方法一般是走一个小trace: 反正就是一个backtracking tree, 能有多大的时间; 当实际上看到duplicate的时候, 直接就开始分析背后的抽象的原因;
这个题目一个很直接的思路是用element based的方法来做, 那么很容易就看出来一个, 1 2a 2b这里, [2a]和[2b]肯定就是duplicate了;
好像可以用之前的那个relative order的方式来做这个题目? 尝试一下;
因为无视order, 所以用size based的思路可能有点问题: 你在当前的position选择了一个数字, 这个并不能提供任何的uniqueness, 比如上层选3, 下层选6, 后者上层选6, 下层选3, 根本就是一样的, 因为是set;
element based的backtracking, 一般tree不是用类似edge表示num这样的思路, 而是直接每一个node是当前path的state; 然后因为是二叉的, 所以左右分别对应pick or not pick就可以了;
不对, edge好像也可以标上一个num, 只不过只标其中(pick的那一个)一个就行了;
最后还是成功的做出来了; 速度是6ms (19%)(去掉debug部分之后的);
这个算法因为是element based, 所以如果你想要表达的是: 如果不满足relative order, 就不pick, 不能直接说continue或者return, 而是应该跟上面的代码那样, 把pick的部分的, 包括do and undo之类的逻辑全部包裹起来就行了;
另外, 这题的base case, 应该是判断pos == nums.length, 而不是length - 1. 因为你pos在最后一个位置的时候, 其实你还没有处理这个位置的数字; 之前也是一再强调, base case看起来代码最少最简单, 但是很多时候在你把整个算法都理解之前, base case是非常难写的, 不要一开始就纠结base case;
另外, 一个重要的忘记说了, 这个题目教会了我做backtracking的正确思路; 我以前做backtrack题目很多时候就是直接在脑子里空想, 这个是很不好的一个习惯, 稍微复杂一点的题目你肯定就想不出来了; 这题我就直接先一个DFS tree画出来; 然后再根据题目的要求, 看看这个tree应该怎么进一步的修理:
比如上面这样, 理解了应该prune掉哪些path之后, 就很好写了;
没有editorial;
To solve this problem, it is helpful to first think how many subsets are there. If there is no duplicate element, the answer is simply 2^n, where n is the number of elements. This is because you have two choices for each element, either putting it into the subset or not. So all subsets for this no-duplicate set can be easily constructed:
num of subset
- (1 to 2^0) empty set is the first subset
- (2^0+1 to 2^1) add the first element into subset from (1)
- (2^1+1 to 2^2) add the second element into subset (1 to 2^1)
- (2^2+1 to 2^3) add the third element into subset (1 to 2^2)
- …
- (2^(n-1)+1 to 2^n) add the nth element into subset(1 to 2^(n-1))
Then how many subsets are there if there are duplicate elements? We can treat duplicate element as a spacial element. For example, if we have duplicate elements (5, 5), instead of treating them as two elements that are duplicate, we can treat it as one special element 5, but this element has more than two choices: you can either NOT put it into the subset, or put ONE 5 into the subset, or put TWO 5s into the subset. Therefore, we are given an array (a1, a2, a3, …, an) with each of them appearing (k1, k2, k3, …, kn) times, the number of subset is (k1+1)(k2+1)…(kn+1). We can easily see how to write down all the subsets similar to the approach above.
分析的还是很到位的, 算法本身的实现, 是之前见过好几次的用iteration来改写returned recursion的思路; 注意一个小问题, 为什么看起来大家都很沉迷于避免recursion? 这个是有原因的, recursion虽然有时候看起来很快(尤其是iteration需要大量的使用collection的时候), recursion是有爆栈的可能性的, 这个就一定程度上限制了其scalability;
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;
}
};
这个count就是数一下有多少个[i];
应该是不难看懂的, 代码本身写的其实非常的干净;
https://leetcode.com/problems/subsets-ii/discuss/30137/Simple-iterative-solution
If we want to insert an element which is a dup, we can only insert it after the newly inserted elements from last step.
vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(), S.end());
vector<vector<int>> ret = {{}};
int size = 0, startIndex = 0;
for (int i = 0; i < S.size(); i++) {
startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;
size = ret.size();
for (int j = startIndex; j < size; j++) {
vector<int> temp = ret[j];
temp.push_back(S[i]);
ret.push_back(temp);
}
}
return ret;
}
刚开始没有看懂;
这个算法设计的还是有点复杂的, 主要是这个size的更新方式, 以及用这个size来控制跳子; 在用这种returned iteration的时候, 很多时候确实是需要像他这里这样, 对于这个dynamic的result的size, 要很敏感;
The characteristics of C++ reference is an outstanding tool for backtracking algorithm!
let us use [1,2,3,4] as an example to explain my solution:
subsets([1,2,3,4]) = [] // push(1) [1, subsets([2,3,4])] // if push N times in subsets([2,3,4]), the pop times is also N, so vec is also [1] after backtrack. // pop(), push(2) [2, subsets([3,4])] // pop(), push(3) [3, subsets([4])] // pop(), push(4) [4, subsets([])] // pop()Accepted 10ms c++ solution use backtracking for Subsets
class Solution {
public:
std::vector<std::vector<int> > subsets(std::vector<int> &nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int> > res;
std::vector<int> vec;
subsets(res, nums, vec, 0);
return res;
}
private:
void subsets(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
res.push_back(vec);
for (int i = begin; i != nums.size(); ++i) {
vec.push_back(nums[i]);
subsets(res, nums, vec, i + 1);
vec.pop_back();
}
}
};
Accepted 10ms c++ solution use backtracking for Subsets II
class Solution {
public:
std::vector<std::vector<int> > subsetsWithDup(std::vector<int> &nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int> > res;
std::vector<int> vec;
subsetsWithDup(res, nums, vec, 0);
return res;
}
private:
void subsetsWithDup(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
res.push_back(vec);
for (int i = begin; i != nums.size(); ++i)
if (i == begin || nums[i] != nums[i - 1]) {
vec.push_back(nums[i]);
subsetsWithDup(res, nums, vec, i + 1);
vec.pop_back();
}
}
};
严格来说这个backtracking不是很适用我之前分析的那些套路, 因为这个你看他update/collect的位置, 并不是在leaf的位置, 而是在每一个node都update;
仔细回忆起来, 有相当长一段时间没有写过这种不是leaf位置更新的recursion了; 很奇葩啊, 想要找到一个好的理论来统一这两种写法, 不过暂时还是想不到; leaf recursion现在理解的还是有点透彻了, 但是这种node recursion, 有点难;
当然, 一个牵强附会的解释是这样: 这题是一个size based, 没错, 每一个node对应的其实是一个position in result; 那么就可能出现我们之前说过的1 2和2 1重复的情况, 因为set对order不敏感, 不过他这里通过一些操作排除掉了; 那么, 他用size based来做一个subset的问题, subset的特点就是你不知道size, 也就是size是不确定的, 所以对应的, 在recursion tree里面, 你根本不知道在哪个level来update; 他的做法就是干脆, 所有的node都update, 然后对应的, 限制住一些不合理的node的出现就行了;
比如你看上面的这个, 第一层选了2之后, 第二层(虽然第二层的begin被更新成了3, 但是实际上的在result里面的pos还是第二个)就不能选1了;
backtrack小思
大概还是思考一下最近做过的这些backtrack问题; 首先一个让我疑惑的问题就是, start和used之间到底是什么关系? PermutationII那个最开始用neighbor order的方法, 那个是一个size based的算法, 但是他那个其实used必不可少, 是因为他每一个iteration(result pos)都是从头开始搜索, 所以如果你不用used, 你就不知道之前被用掉的是什么; 当然, 那个题目之所以要从头开始搜索, 是order matters;
当然, 你肯定想说在permutation第一题怎么没有用used呢? 这个当时也总结过了, 是因为他用swap加上start, 来完成了一个类似used的操作; 所以每一个pos才不需要从头开始搜索, 因为所有还没有被固定位置的, 都在start..end的范围内;
Combinations这一题, 也就是N choose K这一题, 当时以为在start的基础上还要加上一个used, 后来发现start一个就够了; 当时这个算法写的也是size based; 可见在这个情况下, used和start就重合了;
这题我的算法是一个element based的, 所以肯定要用used; 但是真的可以这么绝对吗? 这题之所以要用used, 实际上是为了当比如你在2b的时候, 你要知道2a的情况而已; 事实上, 你在2b的时候你关系1的used吗? 不关心的;
我感觉理解backtracking好像实际上还是要用subproblem的思路来写, 比如1 2a 2b这个, 我在1的处理, pick or not pick, 反正是我自己决定的, 然后决定完了之后就直接向下下潜就行了; 浮上来的时候要undo, 因为假如1前面还有内容, 那么1以及1的右边的内容对包括used和path这种共享变量造成的修改, 不应该被tree更上层的node知道: 他们在他们的位置, 看到的就是应该是everything underneath has not happened yet的状态;
那么同样的, size based, 我在result pos [0]的位置循环pick一个数字; 我pick完了之后, 直接用begin来限制我下面的人只能pick比我的大的; 注意, 这里的begin就不单纯是used, 因为begin之前是可能有un used的东西的; 这里的begin实际上还是帮助了enforce order;
而permutation这种, 因为order有效, 就有其他的思考方式;
感觉讲的还是太零碎了; 不知道有没有更加简练的rule of thumb的思考方式;
写到这里, 我感觉其实我一直以来用leaf的判断, 是因为leaf recursion相对来说是好写一些, 写的多了也熟悉了, 但是不代表node recursion就有问题; 关键还是你决定怎么写了, 然后就开始画tree; 然后再根据题目的要求来思考怎么控制这个tree; size based和element based 的区别, 以及mutation recursion和returned recursion的区别, 还是要稍微尊重一下的;
大胆的猜想一下, 实际上node recursion和leaf recursion很多时候都是可以直接互相转换的? 当然, 我现在只是猜测一下;
Good explanation, and share my iterative method:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ret;
ret.push_back(vector<int>());
sort(nums.begin(), nums.end());
vector<vector<int>> sub;
for (int i = 0; i < nums.size(); ++i) {
if (i == 0 || nums[i] != nums[i-1]) sub = ret;
for (auto& j:sub) j.push_back(nums[i]);
ret.insert(ret.end(), sub.begin(), sub.end());
}
return ret;
}
也是一个比较漂亮的解法:
还是一个returned composition的思路, 然后去重思路比较简单, 你看这个trace, 在2b的时候, 只修改2a已经被包括之后的sub结果, 而2a被添加之前的sub, 是不处理的; 当然具体的实现是依靠一个跨iteration的cache完成的, 这个跟原来的OP的思路比较类似;
I love your solution, though mine is a little different.
void subsetsWithDup(vector<int>& nums, vector<int> res, vector<vector<int>>& ans, int start) {
if (start == nums.size()) {
ans.push_back(res);
return;
}
subsetsWithDup(nums,res,ans,start+1);
while (start + 1 < nums.size() && nums[start] == nums[start+1]) {
res.push_back(nums[start]);
++start;
}
res.push_back(nums[start]);
subsetsWithDup(nums,res,ans,start+1);
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> res;
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
subsetsWithDup(nums,res,ans,0);
return ans;
}
跟我的类似的一个element based的做法, 不过他避免duplicate的思路是先not pick, 然后只pick last; 不对, 看错了, 他这里的这个while不是用来skip的; 比如站在一个node上面, 他的操作是先不pick当前的[start], 然后把所有当前start的run都pick掉, 之后从下一个数字(不是[start]的数字)再继续开始pick; 最后真正发生的就是, 比如有5个2, 那么就从上到下5个2分别pick的是含有5,4,3,2,1个2的path, 也就是2的parity被准确的指定;
思路还是很好的思路, 不过不是很容易复现; 相比之下, 还是我这种直接用neighbor order来对tree进行prune的操作我认为更好理解和掌握; 而且发现一个问题, 他这个思路, 比如5个2, 他每一个2的位置, 都要做一个扫描的操作, 对最后的结果的复杂度会不会有影响? 可能不会, 反正只要保证没有重复, 最后大家的结果数量都是一样的; 加上都是element based, 所以fanning也一样, 但是height一样吗? 好像也是一样的;
https://leetcode.com/problems/subsets-ii/discuss/30166/Simple-python-solution-without-extra-space.
class Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
res = [[]]
S.sort()
for i in range(len(S)):
if i == 0 or S[i] != S[i - 1]:
l = len(res)
for j in range(len(res) - l, len(res)):
res.append(res[j] + [S[i]])
return res
if S[i] is same to S[i - 1], then it needn’t to be added to all of the subset, just add it to the last l subsets which are created by adding S[i - 1]
跟上面一个评论里面类似的思路, 其实还是听巧妙的, 隔代cache的思路;
submission基本波动;
Problem Description
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Difficulty:Medium
Total Accepted:138.2K
Total Submissions:364.8K
Contributor:LeetCode
Companies
facebook
Related Topics
arraybacktracking