BitMask Solution O(2^n)


  • 0
    Z

    public class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums.length == 0 ) return ans;
       Arrays.sort(nums);
        int max  = 1<<nums.length;
        int min = 0;
        HashMap<String, Boolean> v = new HashMap<>();
        for(int i = min;i<max;i++){
            List<Integer> list = new ArrayList<>();
            StringBuilder build = new StringBuilder();
            for(int j = 0;j<nums.length;j++){
                if((i & (1<<j)) != 0) {
                     build.append("#").append(j);
                     list.add(nums[j]);
                }
            }
            String key = build.toString();
            if(v.containsKey(key)) continue;
            v.put(key, true);
            ans.add(list);
        }
        return ans;
    }
    

    }


Log in to reply
 

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