給定一個整型陣列, 你的任務是找到所有該陣列的遞增子序列，遞增子序列的長度至少是2。
範例 1：
輸入：nums = [4,6,7,7]
輸出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
範例 2：
輸入：nums = [4,4,3,2,1]
輸出：[[4,4]]
說明:
題目要找出陣列的所有遞增子序列，所以需要將整個樹結構遍歷一遍。
根據說明中的第三點，本題也需要去重。
根據範例2可以看出，我們要找的是陣列中當前順序下的遞增序列，因此不能對給定陣列進行排序
那就噁心了，要知道我們之前在此類問題中去重考的就是 排序後的相鄰重複值 + used標記陣列
不管沒關係，不能排序也行，那就在單層處理時做手腳
這裡還是需要使用used陣列來記錄單層中使用過的元素
在記錄遍歷值前，需要做以下判斷：
為了實現上述思路，在回溯時不能刪除之前used陣列記錄的值，且used陣列改為在單層遞迴迴圈前定義，這樣每到一層新的遞迴層時，used陣列都會被清空
1、確定回溯函數的引數和返回值
引數時題目給的陣列nums、beingIndex，這裡used陣列在回溯函數裡面定義
無返回值
class Solution {
private:
//定義結果陣列
vector<vector<int>> res;
vector<int> path;
//確定回溯函數的引數和返回值
void backtracking(vector<int>& nums, int beginIndex){
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
}
};
2、確定終止條件
參考 子集問題 ，如需要收集樹結構的所有節點，實際上是不需要返回值的（依靠for迴圈結束即可）
但是，本題有一個要求是：遞增子序列大小至少為2
所以在這裡需要單獨處理一下這個邏輯（嚴格來說也不是終止條件）
class Solution {
private:
//定義結果陣列
vector<vector<int>> res;
vector<int> path;
//確定回溯函數的引數和返回值
void backtracking(vector<int>& nums, int beginIndex){
//（確定終止條件）
//確保遞增子序列大小至少為2
if(path.size() > 2){//2個以上才儲存到結果陣列
res.push_back(path);
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
}
};
3、確定單層處理邏輯
在單層處理時，還是去迴圈遍歷當前層的元素
不過需要初始化used陣列，並且加入當前遍歷值與path陣列中元素比較大小以及判斷當前元素是否被used記錄的邏輯
class Solution {
private:
//定義結果陣列
vector<vector<int>> res;
vector<int> path;
//確定回溯函數的引數和返回值
void backtracking(vector<int>& nums, int beginIndex){
//（確定終止條件）
//確保遞增子序列大小至少為2
if(path.size() > 1){//2個以上才儲存到結果陣列
res.push_back(path);
}
//確定單層處理邏輯
//初始化used陣列，每次進入遞迴都會被重新整理
int used[201] = {0};//題目中說了，數值範圍[-100,100]，因此直接用陣列就行
for(int i = beginIndex; i < nums.size(); ++i){
//判斷邏輯
//path是否為空；當前值是否小於path中最新加入的值；或者當前值是否被記錄於used
if(!path.empty() && nums[i] < path.back() || used[100 + nums[i]] == 1){
continue;//滿足上述條件就跳過
}
used[100 + nums[i]] = 1;//在nums[i]位置記錄出現過當前遍歷值
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
}
};
1、vector::back()用於取陣列最新加入的一個值，這裡用來取上次新增的值並與當前遍歷值進行比較
2、使用陣列來記錄數的話，需要建立能夠容納所有元素個數的大小。然後只需在該元素大小位置處標記元素是否出現過即可
例如：如果遍歷值是2，那麼應該在used陣列的100 + 2，也就是下標為102處記錄1，表示2出現過1次
加100是因為題目所給範圍是[-100,100]，前100是負數值
class Solution {
private:
//定義結果陣列
vector<vector<int>> res;
vector<int> path;
//確定回溯函數的引數和返回值
void backtracking(vector<int>& nums, int beginIndex){
//（確定終止條件）
//確保遞增子序列大小至少為2
if(path.size() > 1){//2個以上才儲存到結果陣列
res.push_back(path);
}
//確定單層處理邏輯
//初始化used陣列，每次進入遞迴都會被重新整理
int used[201] = {0};//題目中說了，數值範圍[-100,100]，因此直接用陣列就行
for(int i = beginIndex; i < nums.size(); ++i){
//判斷邏輯
//path是否為空；當前值是否小於path中最新加入的值；或者當前值是否被記錄於used
if(!path.empty() && nums[i] < path.back() || used[100 + nums[i]] == 1){
continue;//滿足上述條件就跳過
}
used[100 + nums[i]] = 1;//在nums[i]位置記錄出現過當前遍歷值
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};