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.

1. Initialization: We initialize an empty result list (ans) and an empty path list. ans will contain all the valid increasing subsequences, while path will store the current subsequence that is being considered.

2. 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 to ans.

3. Avoiding duplicates: We keep track of 'visited' elements at each level of depth to avoid duplicate subsequences.

4. 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 the path. If the condition is satisfied, we add the current number into the path, call the DFS function for the next index, and then remove the current number from the path.

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!