Subsets - Leetcode

Photo by Artem Shuba on Unsplash

Subsets - Leetcode

Finding subsets of an array using bit manipulation(Power Set) and recursion.

Table of contents

Bit Manipulation

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int len = nums.length;

        for(int n = 0; n < Math.pow(2, len); n++) {
            List<Integer> curList = new ArrayList<>();
            for(int i = 0; i < len; i++) {
                if( (n & (1 << i)) != 0 )
                    curList.add(nums[i]);
            }
            res.add(curList);
        }

        return res;
    }

Recursion

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        f(res, 0, new ArrayList<>(), nums);

        return res;

    }

    private void f(List<List<Integer>> res, int ind, List<Integer> arr, int[] nums) {
        if(nums.length == ind) {
            res.add(new ArrayList<>(arr));
            System.out.println(arr);
            return;
        }

        arr.add(nums[ind]);
        f(res, ind+1, arr, nums);
        arr.remove(arr.size() - 1);
        f(res, ind+1, arr, nums);

    }