491. Increasing Subsequences

Problem:

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:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Analysis:

It's dfs apparently. Since the array can not be sorted, we need to use set to remove duplicates. 

Solution:

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return res;
        dfs(res, new ArrayList<>(), nums, 0, -101);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, int index, int pre) {
        if (list.size() > 1) {
            res.add(new ArrayList<>(list));
        }
        if (index == nums.length)
            return;
        Set<Integer> set = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            if (!set.add(nums[i])) continue;
            if (nums[i] >= pre) {
                list.add(nums[i]);
                dfs(res, list, nums, i + 1, nums[i]);
                list.remove(list.size() - 1);   
            }
        }
    }
}