回溯——491.遞增子序列
給定一個整型數組, 你的任務是找到所有該數組的遞增子序列，遞增子序列的長度至少是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]。
- 給定數組中可能包含重複數字，相等的數字應該被視為遞增的一種情況。
子序列最大的問題就是：不能打破原數組的順序。所以我之前的錯誤思路如下：
private void backtracking(int[] nums, int startIndex, int depth) { // System.out.println("" + depth+ " " + path.toString()); if (path.size() >= 2) { result.add((ArrayList) path.clone()); } int preMax = -101; for (int i = startIndex; i < nums.length; ++i) { if (i > startIndex && nums[i] == preMax) { //System.out.println(path.toString()); continue; } preMax = Math.max(preMax, nums[i]); if (path.isEmpty() || nums[i] >= path.get(path.size()-1)) { path.add(nums[i]); backtracking(nums, i+1, depth+1); path.remove(path.size()-1); } // else { // backtracking(nums, i+1, depth+1); // } } }
這裡我想的是，在回溯樹的一次向下延申中，不能有和當前元素相同的元素出現，即不能同時將2+個相同元素連續加入path中。
但是這樣會出現一個問題：例如數組[1 2 3 4 5 1 1 1 1 1]：
- 對與數組剛開始的1，有path：[1, 1]
- 對於數組的第二個1，也有path：[1,1]
由此可以發現：
本題要求，在回溯樹每一層的遍歷中，是不允許有任一元素重複加入path中。因為number第一次出現時，是從number——last number依次遍歷下去的，這次遍歷就將number第二次出現可能出現的所有path都遍歷過了。所以進行以下處理：
private void backtracking(int[] nums, int startIndex) { //System.out.println("" + depth + " " + path.toString()); if (path.size() >= 2) { result.add((ArrayList) path.clone()); } Set<Integer> preElement = new HashSet<>(); for (int i = startIndex; i < nums.length; ++i) { //在本層回溯樹的遍歷過程中，是不能有元素連續開啟回溯的 if (preElement.contains(nums[i])) { continue; } else { preElement.add(nums[i]); } if (path.isEmpty() || nums[i] >= path.get(path.size()-1)) { path.add(nums[i]); backtracking(nums, i+1); path.remove(path.size()-1); } } }
