78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

1
2
3
4
5
6
7
8
9

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
    
     public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        int n = nums.length;
        for (int i = (int) Math.pow(2, n); i < (int) Math.pow(2, n + 1); i++) {
            // generate bitmasks from 00.000 to 111..111
            String bitmask = Integer.toBinaryString(i).substring(1);
            List<Integer> curr = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (bitmask.charAt(j) == '1') curr.add(nums[j]);
            }
            subsets.add(curr);
        }
        return subsets;
    }
    
     public List<List<Integer>> subsets3(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        dfs(0, nums, current, subsets);
        return subsets;
    }
    
    void dfs(int index, int[] nums, List<Integer> current, List<List<Integer>> subsets) {
        if (index == nums.length) {
             subsets.add(new ArrayList<>(current));
            return;
        }
        
        current.add(nums[index]);
        dfs(index + 1, nums, current, subsets);
        
        current.remove(current.size() - 1);
        dfs(index + 1, nums, current, subsets);
    }
    
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        generateSubsets(0, nums, current, subsets);
        return subsets;
    }
    
    void generateSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> subsets) {
        
        subsets.add(new ArrayList<>(current));
        
        for (int i = index; i < nums.length; i++) {
            current.add(nums[i]);
            generateSubsets(i + 1, nums, current, subsets);
            current.remove(current.size() - 1);
        }
    }
}

Solution 2021-11-22

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        dfs(0, nums, res, curr);
        return res;
    }
    
    void dfs(int index, int[] nums, List<List<Integer>> res, List<Integer> curr) {
        if (index == nums.length) {
            res.add(List.copyOf(curr));
            return;
        }
        
        curr.add(nums[index]);
        
        dfs(index + 1, nums, res, curr);
        
        curr.remove(curr.size() - 1);
        dfs(index + 1, nums, res, curr);
    }
}