Leetcode 78. Subsets

Problem Explanation

This problem is asking to generate all subsets of the given array. Subset means all combinations of the array that don't change the order of integers of the array, but the order of subsets in the main result does not matter.

The problem can be approached using the depth-first search (DFS) approach that starts from an empty subset and then traverses through the rest of the subsets. In each subset, generate all possible subsets with the remaining numbers.

For example, if we have nums = [1, 2, 3], we start with an empty subset []. Then move to next subsets, [1], [1, 2], and then [1, 2, 3]. In between each subset, we recursively go to their own possible subsets, i.e., from [1, 2] we also generate the subset [1, 2, 3].

Algorithm Walkthrough

Here's how the depth-first search (DFS) approach works with nums = [1, 2, 3]:

1. Start from an empty subset [ ].
2. At the first level of recursion, add the first number (1) to the subset.

1
2
3  [ ]
4 / 
5[1] 

3. Generate all subsets including 1:

1
2
3  [ ]
4 / 
5[1] -> [1, 2] -> [1, 2, 3]

4. Move back to the 1st step and try the next number (2):

1
2
3    [ ]
4   /  \
5 [1]  [2] -> [2, 3]

5. Repeat for the next number (3):

1
2
3    [ ]
4   / | \
5 [1] [2] [3]

The subsets we found were: [ ], [1], [1,2], [1,2,3], [2], [2,3], [3].

Each time of the recursive call, we need to add the current subset into the result set and update the subset by adding the current number into it.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  vector<vector<int>> subsets(vector<int>& nums) {
6    vector<vector<int>> result;
7    generateSubsets(nums, 0, {}, result);
8    return result;
9  }
10
11 private:
12  void generateSubsets(const vector<int>& nums, int start, vector<int> subset,
13           vector<vector<int>>& result) {
14    result.push_back(subset);
15
16    for (int i = start; i < nums.size(); ++i) {
17      subset.push_back(nums[i]);  // add current number to subset
18      generateSubsets(nums, i + 1, subset, result); // generate all other combinations
19      subset.pop_back();  // remove current number from subset
20    }
21  }
22};

We will add other language solutions soon.## Python Solution

1
2python
3class Solution:
4    def subsets(self, nums):
5        result = []
6        self.generatesubsets(nums, 0, [], result)
7        return result
8
9    def generatesubsets(self, nums, start, current, result):
10        result.append(list(current))
11        
12        for i in range(start, len(nums)):
13            current.append(nums[i])
14            self.generatesubsets(nums, i + 1, current, result)
15            current.pop()

The Python code implicitly uses a depth-first search approach by means of recursion. Like the earlier C++ solution, it starts with an empty array [], tries combinations with the existing numbers, and then removes the last added number in the iteration of the DFS.

JavaScript Solution

1
2javascript
3const subsets = (nums) => {
4    let result = [];
5    generateSubsets([], 0);
6    
7    function generateSubsets(curr, start){
8        result.push([...curr]);
9        for(let i=start; i< nums.length; i++){
10            curr.push(nums[i]);
11            generateSubsets(curr, i + 1);
12            curr.pop();
13        }
14    }
15    return result;
16};

The JavaScript solution utilizes the same strategy. It first defines a function generateSubsets to generate the subsets using depth-first search. Additionally, it makes use of the JavaScript spread operator (...) to make a copy of the current array and append it to the result.

Java Solution

1
2java
3import java.util.*;
4
5class Solution {
6    public List<List<Integer>> subsets(int[] nums) {
7        List<List<Integer>> result = new ArrayList<>();
8        generateSubsets(result, new ArrayList<>(), nums, 0);
9        return result;
10    }
11    
12    private void generateSubsets(List<List<Integer>> result, ArrayList<Integer> temp, int[] nums, int start) {
13        result.add(new ArrayList<>(temp));
14        for (int i = start; i < nums.length; i++) {
15            temp.add(nums[i]);
16            generateSubsets(result, temp, nums, i + 1);
17            temp.remove(temp.size() - 1);
18        }
19    }
20}

In the Java solution, ArrayList is used to store the current subset and the result. Since Java is pass-by-value, we need to manually make a copy of temp when adding it to the result. For each number, the function recursively explores all possible combinations by including the number in temp. After the recursive call, the number is then removed from temp to backtrack and explore the other possibilities.