# 90.Subsets II (M)

## 1.Description(Medium)

Given a list of numbers that may has duplicate numbers, return all possible subsets

### Notice

* Each element in a subset must be in \_non-descending \_order.
* The ordering between two subsets is free.
* The solution set must not contain duplicate subsets.

**Example**

If S =`[1,2,2]`, a solution is:

```
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
```

## 2.Code

与subset 相比，区别只在于去重。对于当前字符，如果下一个字符与之相等，则过滤掉。与combination sum I II 的区别相同。

```
public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S){
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        if(S==null || S.size()==0){
            return result;
        }
        ArrayList<Integer> path=new ArrayList<Integer>();
        Collections.sort(S);
        dfs(S,0,path,result);
        return result;        
    }

    public void dfs(ArrayList<Integer> S,int startindex,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> result){
        result.add(new ArrayList<Integer>(path));
        for(int i=startindex;i<S.size();i++){
            if(i!=startindex && S.get(i)==S.get(i-1)){
                continue;
            }
            path.add(S.get(i));
            dfs(S,i+1,path,result);
            path.remove(path.size()-1);
        }
    }
```