遞增子序列_Java

題目：遞增子序列

題目描述：

給定一個整型數組, 你的任務是找到所有該數組的遞增子序列，遞增子序列的長度至少是2。

示例:

輸入: [4, 6, 7, 7]

輸出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

說明:

給定數組的長度不會超過15。

數組中的整數範圍是 [-100,100]。

給定數組中可能包含重複數字，相等的數字應該被視為遞增的一種情況。

解題思路：

ps：參考力扣評論區

這道題的難度在于數字會重複，先考慮沒有重複的情況

加入目前數字會産生哪些新序列，隻要周遊目前存在的序列并比較最後一個數字和目前數字，如果目前數字更大則加入産生新的序列

由 1 産生的新序列加上已經存在的序列以及目前數字作為一個新序列起點的情況作為新的結果

最後過濾掉長度不足 2 的序列得到最終結果

加入重複數字後，比如序列 [4,6,7,7] 周遊完前三個數字後可得到

[[4],[4,6],[6],[4,7],[4,6,7],[6,7],[7]]，再加入 7 的話與前三個的組合就會和後面發生重複，是以要避免與前三個組合。利用字典儲存該數字上一次出現時未組合之前結果的長度，當再次出現時隻和該索引以及之後的序列進行組合，這樣就避免了重複。最後去掉長度不足 2 的序列。

代碼實作：

class Solution {
    //回溯法進行求解，當後面的值大于前面的值時，把元素往集合中進行添加
    Set<List<Integer>> list=new HashSet<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
		//List<List<Integer>> list=new ArrayList<>();
		List<Integer> al=new ArrayList<>();
		getRes(al,nums,0);
		return new ArrayList<>(list);
        
    }
	private void getRes(List<Integer> al, int[] nums, int start) {
		if(al.size()>=2) {
            List<Integer> cloneAl=new ArrayList<>(al);
			list.add(cloneAl);
		}
		for(int i=start;i<nums.length;i++) {
			if(al.size()==0 || nums[i]>=al.get(al.size()-1)) {
				//如果此時的值比前一個值大的話，添加到集合中
				al.add(nums[i]);
				getRes(al,nums,i+1);
				al.remove(al.size()-1);
			}
		}
	}
}
           

ps: 不能使用List ，用它進行contains去除重複時會逾時。