491. Non-decreasing Subsequences

Problem

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2.

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Problem Summary

Given an integer array, your task is to find all increasing subsequences of the array, and the length of an increasing subsequence should be at least 2.

Notes:

1. The length of the given array will not exceed 15.
2. The range of integers in the array is [-100,100].
3. The given array may contain duplicate numbers, and equal numbers should be considered as a case of increasing.

Solution Ideas

• Given an array, find all non-decreasing subsequences in this array with length greater than 2. The order of the subsequence and the indices of the elements in the original array must be in order, not reverse order.
• This problem is similar to Problems 78 and 90. Problems 78 and 90 ask for all subsequences; this problem adds the conditions of being non-decreasing and having length greater than 2 on top of those two problems. Two points need attention: elements in the original array may be duplicated, and the final output needs to be deduplicated. Use a map to handle deduplication of the final output, and use DFS traversal to search through duplicate elements in the array. In each DFS, use a map to record the elements that have been traversed, ensuring that duplicate elements do not appear in this round of DFS; when recursing to the next level, another element with the same value but a different index can still be selected. The outer loop should also add a map; this map filters duplicate solutions caused by duplicate elements in each group of solutions. After filtering, the starting points are different, and the final solutions will also be different.
• This problem is similar to Problems 78 and 90, and they can be solved and reviewed together.

Code

package leetcode

func findSubsequences(nums []int) [][]int {
	c, visited, res := []int{}, map[int]bool{}, [][]int{}
	for i := 0; i < len(nums)-1; i++ {
		if _, ok := visited[nums[i]]; ok {
			continue
		} else {
			visited[nums[i]] = true
			generateIncSubsets(nums, i, c, &res)
		}
	}
	return res
}

func generateIncSubsets(nums []int, current int, c []int, res *[][]int) {
	c = append(c, nums[current])
	if len(c) >= 2 {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
	}
	visited := map[int]bool{}
	for i := current + 1; i < len(nums); i++ {
		if nums[current] <= nums[i] {
			if _, ok := visited[nums[i]]; ok {
				continue
			} else {
				visited[nums[i]] = true
				generateIncSubsets(nums, i, c, res)
			}
		}
	}
	c = c[:len(c)-1]
	return
}