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
}