【题目】
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],
[]
]
【解析】
看到这个题目,我立马想起了 【LeetCode】Combinations 解题报告 和 【LeetCode】Subsets 解题报告 。
题意:给定了数组,数组中的数有重复,要求出所有子集。
思路还是回溯。我沿着上道题的思路,分别回溯求长度为0~n的子集。并且在回溯过程中判断重复的子集。
public class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
int[] num = null;
public List<List<Integer>> subsetsWithDup(int[] num) {
this.num = num;
// Sort first!
Arrays.sort(num);
// Add the subsets of length from 0 to num.length by back tracking.
for (int i = 0; i <= num.length; i++) {
backTracking(new ArrayList<Integer>(), 0, i);
}
return ans;
}
public void backTracking(List<Integer> cur, int from, int cnt) {
if (cur.size() == cnt) {
// Find if cur is in the result.
boolean hasSame = false;
int k = ans.size() - 1;
while (k >= 0 && ans.get(k).size() == cnt) {
List<Integer> last = ans.get(k);
int i = 0;
for ( ; i < cnt; i++) {
if (last.get(i) != cur.get(i)) {
break;
}
}
if (i == cnt) {
hasSame = true;
break;
}
k--;
}
// If cur is not the same as last subset, add it to the result set.
if (!hasSame) {
List<Integer> list = new ArrayList<Integer>(cur);
ans.add(list);
}
} else {
// Go on back tracking.
for (int i = from; i < num.length; i++) {
cur.add(num[i]);
backTracking(cur, i + 1, cnt);
cur.remove(new Integer(num[i]));
}
}
}
}