78. Subsets

三刷 06/2022

Version #2 Bit Manipulation

Time O(N*2^N)

Space O(1)

Runtime: 1 ms, faster than 87.63% of Java online submissions for Subsets.

Memory Usage: 42.4 MB, less than 90.42% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        // Given N numbers, the combination of those numbers could be represented by number 0-2^N-1

        int N = nums.length;

        List<List<Integer>> result = new ArrayList<>();

        // e.g. [1] -> [] [1] -> N=1

        for (int mask = 0; mask < (1 << N); mask++) {

            // Given a mask, if the bit is 1, then we should add the number

            List<Integer> sub = new ArrayList<>();

            for (int i = 0; i < N; i++) {

                if (((mask >> i) & 1) == 1) {

                    sub.add(nums[i]);

                }

            }

            result.add(sub);

        }

        return result;

    }

}

二刷 05/2022

Version #1 DFS Recursion - iterate over each number on every layer

Time O(N * 2^N) -> We need O(N) time to copy the result to a new list * 2^N subsets

Space O(N)

Runtime: 2 ms, faster than 29.41% of Java online submissions for Subsets.

Memory Usage: 43.9 MB, less than 7.12% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null) {

            return result;

        }

        dfs(nums, 0, new ArrayList<>(), result);

        return result;

    }

    private void dfs(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result) {

        result.add(new ArrayList<>(path));

        for (int i = startIndex; i < nums.length; i++) {

            path.add(nums[i]);

            dfs(nums, i + 1, path, result);

            path.remove(path.size() - 1);

        }

    }

}

Version #2 DFS - choose adding or not adding each element on every layer

Runtime: 1 ms, faster than 80.34% of Java online submissions for Subsets.

Memory Usage: 43.2 MB, less than 53.28% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null) {

            return result;

        }

        dfs(nums, 0, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {

        if (index == nums.length) {

            result.add(new ArrayList<>(path));

            return;

        }

        // Two possible solutions

        // 1 not choose current index

        dfs(nums, index + 1, path, result);

        // 2 choose current index

        path.add(nums[index]);

        dfs(nums, index + 1, path, result);

        path.remove(path.size() - 1);

    }

}

Version #3 Bit Manipulation

Runtime: 1 ms, faster than 80.34% of Java online submissions for Subsets.

Memory Usage: 43.4 MB, less than 38.72% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        // For each index of nums, we can choose either put it in the set or not

        // 0 -> 0 0 0 -> []

        // 1 -> 0 0 1 -> [1]

        // 2 -> 0 1 0 -> [2]

        // .    . . .     .

        // 2^nums.length - 1

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length == 0) {

            return result;

        }

        for (int i = 0; i < 1 << nums.length; i++) {

            List<Integer> subset = new ArrayList<>();

            int bit = 0;

            while (i >> bit > 0) {

                if (((i >> bit) & 1) == 1) {

                    subset.add(nums[bit]);

                }

                bit++;

            }

            result.add(subset);

        }

        return result;

    }

}           

一刷

Version #3 Bit Manipulation
For a given length of bits, we can use 0 to represent not shown and 1 to represent shown
So a binary number can represent 1 result
Iterate through all possible binary numbers, add the digit when we see 1

100.00 %
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
       
        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> sub = new ArrayList<>();
            int bit = 0;
            while ((i >> bit) > 0) {
                if (((i >> bit) & 1) == 1) {
                    sub.add(nums[bit]);
                }
                bit++;
            }
            result.add(sub);
        }
        return result;
    }
}



Version #1 Iterate through next elements, choose which one to add
Always adding to result list at every level

100.00 %
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        helper(nums, 0, new ArrayList<>(), result);
        return result;
    }
    private void helper(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            helper(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Version #2  Look at current index at each level, decide if we add current element or not
Results are added at the last level