90.Subsets II (M)

https://leetcode.com/problems/subsets-ii/

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);
        }
    }