递增子序列

2020-08-26

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

主要思路：
本题主要考察回溯算法的理解，类似于全排列的思路，根据题目进行剪枝，最主要是如何去重，因为数组中存在重复的数字所以在选择的过程中可能会出现重复的子序列，所以根据去重的思路我们主要分为两种，关于选数的分递归可以用for循环和选与不选两种思路，此处我们Set方法用for循环，剪枝用选与不选的方法
一、Set去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Set<Object> set = new HashSet<>();//去重
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<Integer> path = new ArrayList<>();
		dfs(0,nums,path);
		return res;
    }
    private void dfs(int start, int[] nums,List<Integer> path) {
		if(path.size()>=2&&!set.contains(path)) {
		    //到达最深处拷贝path
			set.add(new ArrayList<>(path));
			res.add(new ArrayList<>(path));
		}
		for(int i = start;i<nums.length;i++) {
			if(path.size()==0||path.get(path.size()-1)<=nums[i]) {
				path.add(nums[i]);
				dfs(i+1, nums,path);
				path.remove(path.size()-1);
			}
		}
		
	}
}

二、剪枝去重
那如何保证没有重复呢？我们需要给「不选择」做一个限定条件，只有当当前的元素不等于上一个选择的元素的时候，才考虑不选择当前元素，直接递归后面的元素。因为如果有两个相同的元素，我们会考虑这样四种情况：

前者被选择，后者被选择
前者被选择，后者不被选择
前者不被选择，后者被选择
前者不被选择，后者不被选择
其中第二种情况和第三种情况其实是等价的，我们这样限制之后，舍弃了第二种，保留了第三种，于是达到了去重的目的。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<Integer> path = new ArrayList<>();
		dfs(0,nums,path,Integer.MIN_VALUE);
		return res;
    }
    private void dfs(int index, int[] nums,List<Integer> path,int last) {
		if(index == nums.length) {
			if(path.size()>=2)
				res.add(new ArrayList<>(path));
			return;
		}
		if(nums[index]>=last) {
			path.add(nums[index]);
			dfs(index+1, nums, path, nums[index]);
			path.remove(path.size()-1);
		}
		if(nums[index]!=last)
			dfs(index+1, nums, path, last);
		
	}
}