Bit Manipulation
Array
Hash Table
Backtracking
Description
Given an integer array nums
, return all the different possible non-decreasing subsequences of the given array with at least two elements . You may return the answer in any order .
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
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def findSubsequences ( self , nums : List [ int ]) -> List [ List [ int ]]:
def dfs ( u , last , t ):
if u == len ( nums ):
if len ( t ) > 1 :
ans . append ( t [:])
return
if nums [ u ] >= last :
t . append ( nums [ u ])
dfs ( u + 1 , nums [ u ], t )
t . pop ()
if nums [ u ] != last :
dfs ( u + 1 , last , t )
ans = []
dfs ( 0 , - 1000 , [])
return ans
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
28 class Solution {
private int [] nums ;
private List < List < Integer >> ans ;
public List < List < Integer >> findSubsequences ( int [] nums ) {
this . nums = nums ;
ans = new ArrayList <> ();
dfs ( 0 , - 1000 , new ArrayList <> ());
return ans ;
}
private void dfs ( int u , int last , List < Integer > t ) {
if ( u == nums . length ) {
if ( t . size () > 1 ) {
ans . add ( new ArrayList <> ( t ));
}
return ;
}
if ( nums [ u ] >= last ) {
t . add ( nums [ u ] );
dfs ( u + 1 , nums [ u ] , t );
t . remove ( t . size () - 1 );
}
if ( nums [ u ] != last ) {
dfs ( u + 1 , last , t );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public :
vector < vector < int >> findSubsequences ( vector < int >& nums ) {
vector < vector < int >> ans ;
vector < int > t ;
dfs ( 0 , -1000 , t , nums , ans );
return ans ;
}
void dfs ( int u , int last , vector < int >& t , vector < int >& nums , vector < vector < int >>& ans ) {
if ( u == nums . size ()) {
if ( t . size () > 1 ) ans . push_back ( t );
return ;
}
if ( nums [ u ] >= last ) {
t . push_back ( nums [ u ]);
dfs ( u + 1 , nums [ u ], t , nums , ans );
t . pop_back ();
}
if ( nums [ u ] != last ) dfs ( u + 1 , last , t , nums , ans );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 func findSubsequences ( nums [] int ) [][] int {
var ans [][] int
var dfs func ( u , last int , t [] int )
dfs = func ( u , last int , t [] int ) {
if u == len ( nums ) {
if len ( t ) > 1 {
ans = append ( ans , slices . Clone ( t ))
}
return
}
if nums [ u ] >= last {
t = append ( t , nums [ u ])
dfs ( u + 1 , nums [ u ], t )
t = t [: len ( t ) - 1 ]
}
if nums [ u ] != last {
dfs ( u + 1 , last , t )
}
}
var t [] int
dfs ( 0 , - 1000 , t )
return ans
}
GitHub