Java 10 lines solution using bit manipulation

  • 0

    So basically you relate every subset to a binary number, one bit of 1 in the binary number means the corresponding element in 'nums[]' should be kept, and a 0 bit means not. In the example, 000 corresponds to [ ], 001 is [3], 011 is [2,3], and 111 is [1,2,3].
    Then you loop i over [000, 111] which is [0, 7]. In each iteration, you need to use bit manipulation to determine all the bit in i's binary form: loop j over [0, nums.length], to get the digits of i in j's position, you rightshift i by j and then bitwise 'and' 1.
    If one bit is 1, add the corresponding element of 'nums[]' to a solution subset.
    After a j loop, you get one solution subset. After i loops, you got all the subsets.


    public List<List<Integer>> subsets(int[] nums) {
        long bound = (long)Math.pow(2, nums.length);
        List<List<Integer>> sol = new ArrayList<List<Integer>>();
        for (int i = 0; i < bound; i++) {
            List<Integer> onesol = new ArrayList<Integer>();
            for (int j = 0; j < nums.length; j++) {
                if (((i >> j) & 1) == 1) onesol.add(nums[j]);
        return sol;

Log in to reply

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