My simpler Java solution using Bit Manipulation with O(nlog(n)) time complexity and O(1) space complexity


  • 0
    Y
    public List<List<Integer>> subsets(int[] nums) {
        int numOfElements = 1 << nums.length;
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        results.add(new ArrayList<Integer>());
        for(int i = 1; i < numOfElements; i++) {
            List<Integer> element = new ArrayList<Integer>();
            int temp = i;
            int index = 0;
            /* I use a temp to operate i which stands for i th element of results. In this way, it doesn't need to do comparison when temp is 0.*/
            while(temp != 0) {
              if((temp & 0x1 ) == 1)
                element.add(nums[index]);
              temp = temp >>> 1;
              index++;
            }
            results.add(element);
        }
        return results;     
    }

  • 0
    D

    Typically we assume n is nums.length, not 1 << nums.length.


  • 0
    A

    The time complexity in your title is incorrect. It's O(2^n(logn)). Which is a little bit more efficient than the O(n*2^n) solutions for the same problem, but not O(nlogn).


Log in to reply
 

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