Java, bit-manipulation with explanation


  • 0
    M
    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            int max_res = 1 << nums.length;
            
            List<List<Integer>> answer = new LinkedList<>();
            for (int i = 0; i < max_res; i++) {
                List<Integer> subset = new LinkedList<>();
                for (int bit = 0; bit < nums.length; bit++) {
                    if (((i >> bit) & 1) == 1) subset.add(nums[bit]);
                }
                answer.add(subset);
            }
            
            return answer;
        }
    }
    

    We use the fact that in binary, numbers are represented as

    0000
    0001
    0010
    0011
    0100
    ...
    

    For each of the numbers above, if bit N is 1, then we will add the N-th element to the subset.

    Note: This solution is limited to 31 elements in num. Anything above that will cause an integer overflow.


Log in to reply
 

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