题目描述

给你一个整数数组 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

解题思路

想法有两个，一个是动态规划，使用二维 dp 数组来存储每个位置的递增子序列；另一个是回溯算法，尝试所有可能的子序列，把每一个满足条件的子序列加入结果集。

而动态规划后其实也需要遍历所有可能的子序列，所以最终考虑使用回溯算法来实现。

这里问题的关键在于如何避免重复的子序列。首先用递归查找所有非递减子序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findSubsequences(nums []int) [][]int {
	tmp := []int{}
	ans := [][]int{}
	var backtrack func(index int)
	backtrack = func(index int) {
		if index == len(nums) {
			if len(tmp) >= 2 {
				ans = append(ans, make([]int, len(tmp)))
				copy(ans[len(ans)-1], tmp)
			}
			return
		}

		if len(tmp) == 0 || nums[index] >= tmp[len(tmp)-1] {
			tmp = append(tmp, nums[index])
			backtrack(index + 1)
			tmp = tmp[:len(tmp)-1]
		}

        backtrack(index + 1)		
	}

	backtrack(0)
	return ans
}

这里通过 len(tmp) == 0 || nums[index] >= tmp[len(tmp)-1] 来判断是否可以将当前数字加入到子序列中，如果可以，则递归调用 backtrack 继续查找下一个数字。

当然上面的实现会有重复的子序列，因为没有处理重复数字的情况。为了避免重复，有两种方法，一种比较好理解，就是后处理结果集。也就是每次要添加 tmp 到 ans 前可以判断是否已经存在相同的子序列。判断的实现有比较多的方案：

  • 暴力遍历，依次对比，时间复杂度是 O(n^2)
  • 切片转换为 string，然后使用 map 来存储已经存在的子序列
  • 直接计算 tmp 的哈希值，使用 map 来存储已经存在的子序列

除了后处理结果集外，另一种方法是在递归过程中直接跳过重复的数字。这里需要仔细思考一下为什么会产生重复的子序列。假设当前数字是 nums[i0] = x, nums[i1] = x, nums[i2] = x+1，那么在递归过程中，当处理到 i0 时，可以选择加入 x 继续递归，也可以选择不加入 x 继续递归；当不加入 x 继续递归后处理到 i1 时，如果也选择加入 x，就会产生重复的子序列。也就是说其实就是发生了 i0, i2 和 i1, i2 的重复。

这里进一步考虑其根本问题在于 i0 和 i1 重复的问题，考虑出现两个相同元素时的情况：

  • 前者被选择，后者被选择
  • 前者被选择，后者不被选择
  • 前者不被选择，后者被选择
  • 前者不被选择，后者不被选择

其中第二和第三种情况会产生重复的子序列，所以更进一步的思考，就是对 “不选择” 的情况进行一些限定，确保在处理到相同元素时，只选择其中一个进行递归。具体来说就是，当前数组如果跟已经选择的数字最后一位相同，则忽略到不选择当前数字的这种情况。具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func findSubsequences(nums []int) [][]int {
	tmp := []int{}
	ans := [][]int{}
	var backtrack func(index int)
	backtrack = func(index int) {
		if index == len(nums) {
			if len(tmp) >= 2 {
				ans = append(ans, make([]int, len(tmp)))
				copy(ans[len(ans)-1], tmp)
			}
			return
		}

		if len(tmp) == 0 || nums[index] >= tmp[len(tmp)-1] {
			tmp = append(tmp, nums[index])
			backtrack(index + 1)
			tmp = tmp[:len(tmp)-1]
		}

		if len(tmp) == 0 || nums[index] != tmp[len(tmp)-1] { // 只在当前数字不等于最后一个数字时才考虑不选择当前数字
			backtrack(index + 1)
		}
	}

	backtrack(0)
	return ans
}

因为有递归的存在可能不是很好理解，所以给不选择的情况做限定条件的方法这里值得反复思考一下。

换个角度去理解这个问题，以 [4, 6, 7, 7] 为例，先用树去模拟整个查找的过程：

subsequences-tree

每一层表示从剩下的数字中选择一个数字加入到子序列中。树的层高就表示子串的长度，树的每一层表示从剩下的数字中选择一个数字加入到子序列中。可以看到，树的每一层都可以选择是否加入当前数字，如果加入则继续递归查找下一个数字，如果不加入则直接跳过当前数字。而在每一层选择数字的时候如果发生了重复，就会产生相同的子序列，而如果不同层选择的数字相同则不影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func findSubsequences(nums []int) [][]int {
	tmp := []int{}
	ans := [][]int{}
	var backtrack func(index int)
	backtrack = func(index int) {
		if len(tmp) >= 2 {
			ans = append(ans, make([]int, len(tmp)))
			copy(ans[len(ans)-1], tmp)
		}

		m := make(map[int]struct{})
		for i := index; i < len(nums); i++ {
			if len(tmp) == 0 || nums[i] >= tmp[len(tmp)-1] {
				if _, ok := m[nums[i]]; !ok {
					tmp = append(tmp, nums[i])
					backtrack(i + 1)
					tmp = tmp[:len(tmp)-1]
					m[nums[i]] = struct{}{}
				}
			}
		}
	}

	backtrack(0)
	return ans
}

上面的代码用 map 来记录当前层已经选择过的数字，避免重复的子序列。每次递归时，先将当前子序列加入结果集，然后遍历剩下的数字，如果当前数字可以加入到子序列中且没有被选择过，则加入到子序列中并继续递归。