Leetcode 491. Increasing Subsequences
Problem explanation
We are given an array of integers. Our task is to find all possible increasing subsequences from this array. An increasing subsequence is a sequence in which all the integers are in strictly increasing order.
For example, if the input array is [4, 6, 7, 7]
, some of the possible increasing subsequences are [4, 6]
, [4, 6, 7]
, [4, 6, 7, 7]
, [6, 7, 7]
and so on.
Approach
The solution uses a depth first search (DFS) approach to solve this problem. We start from the first integer and then explore all possible subsequences starting with this integer. Once we have explored all possibilities with the first integer, we move to the next integer and repeat the process. We keep track of the visited integers in a set to avoid duplicate subsequences.
The process can be best visualized through an example. Consider the array [4, 6, 7, 7]
. Here is how the DFS would look like in this case (iterations are indented for clarity):
1 2 3Start with 4 4 Choose 6 5 Add [4, 6] to result 6 Choose 7 7 Add [4, 6, 7] to result 8 Choose 7 9 Add [4, 6, 7, 7] to result 10 Backtrack to 4 11 Choose 7 12 Add [4, 7] to result 13 Choose 7 14 Add [4, 7, 7] to result
Then, go to the next integer, 6
, and repeat the above process.
Solution
Here are the coding solutions in each of the asked languages. In addition to the DFS, we use an integer set to keep track of already visited integers and to avoid duplicate subsequences.
Python
1 2python 3class Solution: 4 # Function to solve the problem 5 def findSubsequences(self, nums): 6 ans = [] 7 self.dfs(nums, 0, [], ans) 8 return ans 9 10 # Helper function to perform DFS 11 def dfs(self, nums, index, path, ans): 12 if len(path) > 1: 13 ans.append(path) 14 visited = set() 15 for i in range(index, len(nums)): 16 if i != index and nums[i] in visited: 17 continue 18 visited.add(nums[i]) 19 if not path or nums[i] >= path[-1]: 20 self.dfs(nums, i+1, path+[nums[i]], ans)
Java
1
2java
3public class Solution {
4 private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> ans) {
5 if (path.size() > 1) {
6 ans.add(new ArrayList<>(path));
7 }
8 Set<Integer> visited = new HashSet<>();
9 for (int i = index; i < nums.length; i++) {
10 if (visited.contains(nums[i])) {
11 continue;
12 }
13 visited.add(nums[i]);
14 if (path.isEmpty() || nums[i] >= path.get(path.size() - 1)) {
15 path.add(nums[i]);
16 dfs(nums, i + 1, path, ans);
17 path.remove(path.size() - 1);
18 }
19 }
20 }
21
22 public List<List<Integer>> findSubsequences(int[] nums) {
23 List<List<Integer>> ans = new ArrayList<>();
24 dfs(nums, 0, new ArrayList<Integer>(), ans);
25 return ans;
26 }
27}
JavaScript
1
2javascript
3class Solution {
4 dfs(nums, index, path, ans) {
5 if (path.length > 1) {
6 ans.push([...path]);
7 }
8 const visited = new Set();
9 for (let i = index; i < nums.length; i++) {
10 if (visited.has(nums[i])) {
11 continue;
12 }
13 visited.add(nums[i]);
14 if (path.length === 0 || nums[i] >= path[path.length - 1]) {
15 path.push(nums[i]);
16 this.dfs(nums, i + 1, path, ans);
17 path.pop();
18 }
19 }
20 }
21
22 findSubsequences(nums) {
23 const ans = [];
24 this.dfs(nums, 0, [], ans);
25 return ans;
26 }
27}
C++
1
2c++
3#include<vector>
4#include<set>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int> > findSubsequences(vector<int>& nums) {
10 vector<vector<int> > ans;
11 vector<int> path;
12 dfs(nums, 0, path, ans);
13 return ans;
14 }
15
16private:
17 void dfs(vector<int>& nums, int index, vector<int>& path, vector<vector<int> >& ans) {
18 if (path.size() > 1) {
19 ans.push_back(path);
20 }
21 set<int> used;
22 for (int i = index; i < nums.size(); i++) {
23 if (used.count(nums[i])) {
24 continue;
25 }
26 used.insert(nums[i]);
27 if (path.empty() || nums[i] >= path.back()) {
28 path.push_back(nums[i]);
29 dfs(nums, i + 1, path, ans);
30 path.pop_back();
31 }
32 }
33 }
34};
C#
1
2csharp
3public class Solution {
4 private void DFS(int[] nums, int index, IList<int> path, IList<IList<int>> ans) {
5 if (path.Count > 1) {
6 ans.Add(new List<int>(path));
7 }
8 HashSet<int> visited = new HashSet<int>();
9 for (int i = index; i < nums.Length; i++) {
10 if (visited.Contains(nums[i])) {
11 continue;
12 }
13 visited.Add(nums[i]);
14 if (path.Count == 0 || nums[i] >= path[path.Count - 1]) {
15 path.Add(nums[i]);
16 DFS(nums, i + 1, path, ans);
17 path.RemoveAt(path.Count - 1);
18 }
19 }
20 }
21
22 public IList<IList<int>> FindSubsequences(int[] nums) {
23 IList<IList<int>> ans = new List<IList<int>>();
24 DFS(nums, 0, new List<int>(), ans);
25 return ans;
26 }
27}
That concludes our in-depth explanation and coding solutions for finding all possible increasing subsequences from a given array. Before moving on, let's break down the crucial parts of the solution code.
In general, the goal of each solution in Python, JavaScript, Java, C++, and C# is to obtain all distinct, increasing subsequences of an array. They all follow the similar logic.
-
Initialization: We initialize an empty result list (
ans
) and an empty path list.ans
will contain all the valid increasing subsequences, whilepath
will store the current subsequence that is being considered. -
DFS Function: For each value in the array, we explore all possible subsequences where this value can be used, leveraging depth-first-search (DFS). In each DFS function call, we first check if the current
path
has more than one element. If yes, we append it toans
. -
Avoiding duplicates: We keep track of 'visited' elements at each level of depth to avoid duplicate subsequences.
-
Condition check: For every index from the current index to the end of the array, if the number at this index has been visited, we continue to the next index. Otherwise, we add the current number to the visited set and check if the
path
is empty or the current number is greater than or equal to the last number in thepath
. If the condition is satisfied, we add the current number into thepath
, call the DFS function for the next index, and then remove the current number from thepath
.
The complexity of these solutions is approximately O(N*2^N), where N is the length of the input array. This is because, at worst case, these solutions will go through all subsets of the array. This exponential time complexity is acceptable as the problem constraint says the length of the given integer array will not exceed 15.
These solutions are very powerful and flexible, as they can easily be adapted to other related problems, such as finding all possible subsequences of a certain length or with a certain sum. Enjoy coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.