package com.fishercoder.solutions;

import java.util.*;

/**
 * 491. Increasing Subsequences
 *
 * 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.
 */
public class _491 {

    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums == null || nums.length == 1) return new ArrayList<>();
        Set<List<Integer>> answer = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        return new ArrayList<>(backtracking(nums, 0, list, answer));
    }

    private Set<List<Integer>> backtracking(int[] nums, int start, List<Integer> currList, Set<List<Integer>> answer) {
        if (currList.size() >= 2) {
            answer.add(new ArrayList<>(currList));
        }
        for (int i = start; i < nums.length; i++) {
            if (currList.size() == 0 || currList.get(currList.size()-1) <= nums[i]) {
                currList.add(nums[i]);
                backtracking(nums, i + 1, currList, answer);
                currList.remove(currList.size()-1);
            }
        }
        return answer;
    }

}

package com.fishercoder.solutions;

import java.util.*;

/**
 * 491. Increasing Subsequences
 *
 * 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.
 */
public class _491 {

    /**I made it by myself this time! Cheers!*/
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums == null || nums.length == 1) return new ArrayList<>();
        Set<List<Integer>> answer = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        return new ArrayList<>(backtracking(nums, 0, list, answer));
    }

    private Set<List<Integer>> backtracking(int[] nums, int start, List<Integer> currList, Set<List<Integer>> answer) {
        if (currList.size() >= 2) {
            answer.add(new ArrayList<>(currList));
        }
        for (int i = start; i < nums.length; i++) {
            if (currList.size() == 0 || currList.get(currList.size()-1) <= nums[i]) {
                currList.add(nums[i]);
                backtracking(nums, i + 1, currList, answer);
                currList.remove(currList.size()-1);
            }
        }
        return answer;
    }

}

add emotional comments