[LeetCode] 491. Increasing Subsequences

轉自LeetCode

Given an integer array nums, return all the different possible increasing subsequences of the given array with at least two elements. You may return the answer in any order.

The given array may contain duplicates, and two equal integers should also be considered a special case of increasing sequence.

 

Example 1:

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

Example 2:

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

 

Constraints:

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

Solution

這題和 90. Subsets II  類似，但差別在於不需要先去 sort

以 [4,1,2,3,4] 為例，在 Subsets II 那題，[4,1,2,3] 和 [1,2,3,4] 是一樣的

所以必須先 sort 然後配合 set 來過濾

但在這題，因為是要找 increasing 的 subsequence

所以 [4,1,2,3] 是不會出現的，在過濾條件中就會直接被過濾

因為是要求排列組合，所以用DFS來解

kotlin

	class Solution {
	val ans = mutableListOf<List<Int>>()
	fun findSubsequences(nums: IntArray): List<List<Int>> {
	dfs(0, nums, emptyList())
	return ans
	}
	fun dfs(start: Int, nums: IntArray, cmb: List<Int>) {
	if(cmb.size > 1) {
	ans.add(cmb)
	}
	val set = mutableSetOf<Int>()
	for(i in start..nums.lastIndex) {
	if((cmb.isNotEmpty() && nums[i] < cmb.last()) || set.contains(nums[i])) {
	continue
	}
	set.add(nums[i])
	dfs(i+1, nums, cmb+listOf(nums[i]))
	}
	}
	}

view raw increasing_subsequences.kt hosted with ❤ by GitHub