Subsets II 18
Question
Given a list of numbers that may has duplicate numbers, return all possible subsets.
Example
If S = [1,2,2], a solution is:
[ [2],
[1],
[1,2,2],
[2,2],
[1,2],
[] ]
Challenge
Can you do it in both recursively and iteratively?
Solution
Recursion: 与Subsets 17类似,但是因为有重复元素,为了避免出现重复解,有几点需要注意。
1) 将所有重复元素排在一起,因此首先对输入数组进行排序
2) 避免重复的方法为:重复元素只能取第一个元素,因此在加入元素前要判断该元素值是否和之前元素相等。
Non-Recursion:
代码如下:
Recursion:
class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
//当相同值元素排列在一起时下面的避免重复方法才有效,因此需要提前对S进行排序。
Collections.sort(S);
if(S == null || S.size() == 0){
return result;
}
helper(result, list, S, 0);
return result;
}
public void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, ArrayList<Integer> S, int pos){
result.add(new ArrayList<Integer>(list));
//连续相同元素在一起时,若第一个没有被加入list,则不能把后面同值元素先加入,否则会出现重复。
for(int i = pos; i < S.size(); i++){
if(i != pos && S.get(i) == S.get(i-1)){
continue;
}
list.add(S.get(i));
helper(result, list, S, i+1);
list.remove(list.size()-1);
}
}
}