Java solution using bit manipulation


  • 9
    P
    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] num) {
            Arrays.sort(num);
            List<List<Integer>> lists = new ArrayList<>();
            int subsetNum = 1<<num.length;
            for(int i=0;i<subsetNum;i++){
                List<Integer> list = new ArrayList<>();
                boolean illegal=false;
                for(int j=0;j<num.length;j++){
                    if((i>>j&1)==1){
                        if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){
                            illegal=true;
                            break;
                        }else{
                            list.add(num[j]);
                        }
                    }
                }
                if(!illegal){
                   lists.add(list); 
                }
                
            }
            return lists;
        }
    }
    

    The idea is using every bit to represent one element in the set. The total number is 2 to num.length. Then we need to avoid duplicates. After we sort the array, the same number will be adjacent to each other.

    For example the set is {1,1,1}. We can get subset {} and {1} first. That's great.
    Then we need to pay attention. Suppose we have a subset x, which including the second 1 but not the first 1, x is a duplicate.
    That's why I write the predicate:
    if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){
    illegal=true;
    break;
    }

    Hope someone can explain it better. I will go to gym now.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.