作者:
Rushia (みけねこ的鼻屎)
2023-01-21 02:56:42※ 引述《pandix (麵包屌)》之銘言:
: 491. Non-decreasing Subsequences
: 給你一個 array nums,要你回傳他的所有非嚴格遞增的 subsequences,順序任意
: subsequence 長度至少要是 2
: 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]]
: 思路:
1.看到要求所有的可能性而且測資的數量很小,基本上百分之百是用回溯法窮舉。
2.用回溯法可以輕易的求出所有的子序列組合,有問題的是[4,6,x,7]和[4,6,7,x]
都是[4,6,7]算是同一個,我們要對他去重。
3.去重的辦法就是用一個Set來記錄當前起點後面的數字,如果遇到已經用過的就跳
過就可以過濾掉上面那種case。
Java Code: