Java bitset + DFS and backtracking


  • 0
    Z
    /*bitset.length() is logical size, size() is allocated bits.*/
    public List<List<Integer>> subsets(int[] nums){
        if(nums == null) return null;
        Arrays.sort(nums);
        
        List<List<Integer>> ret = new ArrayList<>();
        // Set<Integer> set = new HashSet<>(); hash set is slow. 
        BitSet set = new BitSet(nums.length);
        accumulate(nums, set, ret, 0); // backtracking  + dfs, accumulate
        
        return ret;
    }
    
    void accumulate(int[] ns, BitSet set, List<List<Integer>> acc, int level){
        if(level == ns.length){
            List<Integer> tmp = new ArrayList<>();
            for(int i =0; i <ns.length; i ++)
                if(set.get(i))
                    tmp.add(ns[i]);
                    
            acc.add(tmp);
            return ;
        }
    
        set.set(level);
        accumulate(ns, set, acc, level + 1);
        
        set.clear(level);
        accumulate(ns, set, acc, level + 1);
    }

Log in to reply
 

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