491-递增子序列.md

491. 递增子序列

leecode原题

题目

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例

示例 1:

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2:

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

解题思路

思路

本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑！

本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比，我用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：

实现

源码

var (
	res  = make([][]int, 0) // 存放最终结果
	path = make([]int, 0)   // 存放中间临时结果
)

func backtracking(nums []int, startIndex int) {
	if len(path) > 1 {
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)
	}
	set := make(map[int]int, 0) // 记录该层数值是否已经被使用过
	for i := startIndex; i < len(nums); i++ {
		//分两种情况判断：
		//一，当前取的元素小于子集的最后一个元素，则继续寻找下一个适合的元素
		//或者二，当前取的元素在本层已经出现过了，所以跳过该元素，继续寻找
		if (len(path) > 0 && nums[i] < path[len(path)-1]) || (set[nums[i]] == 1) {
			continue
		}
		path = append(path, nums[i])
		set[nums[i]] = 1
		backtracking(nums, i+1)
		path = path[:len(path)-1]
	}
}

func findSubsequences(nums []int) [][]int {
	res = make([][]int, 0) // 存放最终结果
	path = make([]int, 0)  // 存放中间临时结果
	backtracking(nums, 0)
	return res
}