My 2 Java solution, iterative and bit manipulation


  • 1

    I tried to use iterative method first. The idea is to start from all the possible subset of one element, and then take next element into consideration.
    Running time is 2ms.

    public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> r = new ArrayList<List<Integer>>();
            r.add(new ArrayList<Integer>());//add empty subset
            if(nums.length==0) return r;
            
            for(int num:nums){
                int k=r.size();//initial value:2
                
                r.add(Arrays.asList(num));
                int start=1;
                for(int j=start;j<k;j++){
                    List<Integer> temp_list= new ArrayList<Integer>(r.get(j));
                    temp_list.add(num);
                    r.add(temp_list);
                }
            }
            return r;
        }
    

    Next, I tried to use bit manipulation, which is the smartest way to solve this question.
    Its running time is 1ms, and it beats 93% submissions.

     public List<List<Integer>> subsets(int[] nums) {
            //bottom-up
            List<List<Integer>> r = new ArrayList<List<Integer>>();
            r.add(new ArrayList<Integer>());
            if(nums.length==0) return r;
            int s=(int)Math.pow(2,nums.length);
            
            for(int i=1;i<s;i++){
                List<Integer> temp_list = new ArrayList<Integer>();
                for(int j=0;j<nums.length;j++){
                    if(((i>>j)&1)==1)
                        temp_list.add(nums[j]);
                }
                r.add(temp_list);
            }
            return r;
        }
    

Log in to reply
 

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