Iteration + bitops + recursion


  • 0
    Z
    
    /**
     * Use integer to represent 0 to 2^63.
     * Or, use iteration: clone result of last ieration and clone, add new element there.
     * Or, use recursion (though no much point)
     */
    public class Solution {
        public List<List<Integer>> subsets(int[] ns) {
            return recur(ns, 0);
        }
        
        private List<List<Integer>> recur(int [] ns, int start){
            if(start == ns.length){
                List<List<Integer>> empty = new ArrayList<>();
                empty.add(new ArrayList<>());
                return empty;
            }
            
            List<List<Integer>> set = recur(ns, start +1);
            int size = set.size();
            for(int i =0; i < size; i ++){
                List<Integer> clone = new ArrayList(set.get(i));
                clone.add(ns[start]);
                set.add(clone);
            }
            
            return set;
        }
        
        public List<List<Integer>> subsets_iter(int[] ns) {
            List<List<Integer>> set = new ArrayList<>();
            set.add(new ArrayList<>());
            
            for(int n: ns){
                int size = set.size();
                for(int i =0; i < size; i ++){
                    List<Integer> clone = new ArrayList(set.get(i));
                    clone.add(n);
                    set.add(clone);
                }
            }
            
            return set;
        }
        
        public List<List<Integer>> subsets_bitops(int[] ns) {
            long limit = 1 << ns.length;
            List<List<Integer>> ret = new ArrayList<>();
            
            for(long i =0; i < limit; i ++){
                List<Integer> set = new ArrayList<>();
                ret.add(set);
                for(int j =0; j < ns.length; j ++){
                    if(isSet(i, j))
                        set.add(ns[j]);
                }
            }
            
            return ret;    
        }
        
        boolean isSet(long n, int i){
            return ((1 << i) & n) != 0  ;
        }
    }

Log in to reply
 

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