［抄题］：
Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .
Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
- The length of the given array will not exceed 15.
- The range of integer in the given array is [-100,100].
- The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
［思维问题］：
排序没用，同一个7会被算2次，出现2个[4,7]。所以要用set<list>去重
［英文数据结构或算法，为什么不用别的数据结构或算法］：
新建数组，里面的参数是集合就行 很随意
new ArrayList(res);［一句话思路］：
backtracing的函数里必须把数组完全地for一遍，否则不算完全的深度搜索。
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 主函数里先对新变量参数命好名，求结果时可以直接拿出来用
- cur.size() >= 2时即可回收
［二刷］：
括号里参数传list的时候，必须写new ArrayList(set)
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
backtracing的函数里必须把数组完全地for一遍，否则不算完全的深度搜索。
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［算法思想：迭代/递归/分治/贪心］：
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
[潜台词] ：
// package whatever; // don't place package name! import java.io.*;
import java.util.*;
import java.lang.*; class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
//initialization: result, set
List<Integer> cur = new ArrayList<Integer>();
Set<List<Integer>> set = new HashSet<>(); //dfs
dfs(0, nums, cur, set); //return result
List<List<Integer>> result = new ArrayList(new ArrayList(set));
return result;
} public void dfs(int index, int[] nums, List<Integer> cur, Set<List<Integer>> set) {
//add if cur.size() >= 2
if (cur.size() >= 2) set.add(new ArrayList(cur)); //for each number in nums, do backtracing
for (int i = index; i < nums.length; i++) {
//add to cur if cur is null or the next num is bigger
if (cur.size() == 0 || nums[i] >= cur.get(cur.size() - 1)) {
cur.add(nums[i]);
dfs(i + 1, nums, cur, set);
cur.remove(cur.size() - 1);
}
}
}
} class driverFuction {
public static void main (String[] args) {
Solution answer = new Solution();
int[] nums = {4, 6, 7, 7};
List<List<Integer>> result = answer.findSubsequences(nums);
System.out.println(result);
}
}