package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/increasing-subsequences/
 */
public class Problem491 {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        Set<List<Integer>> result = new HashSet<>();
        findSubsequences(list, result);
        return new ArrayList<>(result);
    }

    private static void findSubsequences(List<Integer> nums, Set<List<Integer>> result) {
        if (nums.size() <= 1) {
            return;
        }
        result.add(nums);
        for (int i = 0; i < nums.size(); i++) {
            List<Integer> newList = new ArrayList<>();
            if (i - 1 >= 0) {
                newList.addAll(nums.subList(0, i));
            }
            if (i + 1 <= nums.size() - 1) {
                newList.addAll(nums.subList(i + 1, nums.size()));
            }
            findSubsequences(newList, result);
        }
    }

    public static void main(String[] args) {
        Problem491 prob = new Problem491();
        System.out.println(prob.findSubsequences(new int[]{1, 1, 1})); // [[1, 1], [1, 1, 1]]
        System.out.println(prob.findSubsequences(new int[]{1, 2, 2})); // [[1, 2], [2, 2], [1, 2, 2]]
        System.out.println(prob.findSubsequences(new int[]{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]]
        System.out.println(prob.findSubsequences(new int[]{4, 3, 2, 1})); // []
        System.out.println(prob.findSubsequences(new int[]{4, 3, 1, 2})); // [[1, 2]]
        System.out.println(prob.findSubsequences(new int[]{4, 1, 3, 2})); // [[1, 2], [1, 3]]
    }
}

@@ -44,33 +44,8 @@
 st;%0A
-import java.util.Arrays;%0A
 impo
@@ -270,35 +270,8 @@
 ) %7B%0A
-        Arrays.sort(nums);%0A
     
@@ -461,24 +461,46 @@
 uences(list,
+ 0, new ArrayList%3C%3E(),
  result);%0A  
@@ -604,16 +604,45 @@
 r%3E nums,
+ int idx, List%3CInteger%3E accu,
  Set%3CLis
@@ -675,28 +675,28 @@
     if (
-nums
+accu
 .size() 
 %3C= 1) %7B%0A
@@ -691,12 +691,12 @@
 e() 
-%3C= 1
+%3E= 2
 ) %7B%0A
@@ -709,20 +709,30 @@
       re
-turn
+sult.add(accu)
 ;%0A      
@@ -739,34 +739,8 @@
   %7D%0A
-        result.add(nums);%0A
     
@@ -756,17 +756,19 @@
 int i = 
-0
+idx
 ; i %3C nu
@@ -801,191 +801,166 @@
     
-List%3CInteger%3E newList = new ArrayList%3C%3E();%0A            if (i - 1 %3E= 0) %7B%0A                newList.addAll(nums.subList(0, i));%0A            %7D%0A            if (i + 1 %3C= nums.size() - 1) %7B%0A
+if (!accu.isEmpty()) %7B%0A                if (accu.get(accu.size() - 1) %3C= nums.get(i)) %7B%0A                    List%3CInteger%3E newAccu = new ArrayList%3C%3E(accu);%0A    
     
@@ -978,51 +978,27 @@
  new
-List
+Accu
 .add
-All
 (nums.
-subList(i + 1, nums.size()
+get(i
 ));%0A
@@ -1003,28 +1003,24 @@
 ;%0A          
-  %7D%0A
             
@@ -1013,26 +1013,24 @@
             
-  
 findSubseque
@@ -1039,14 +1039,27 @@
 es(n
-ewList
+ums, i + 1, newAccu
 , re
@@ -1077,715 +1077,227 @@
     
-%7D%0A
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem491 prob = new Problem491();%0A        System.out.println(prob.findSubsequences(new int%5B%5D%7B1, 1, 1%7D)); // %5B%5B1, 1%5D, %5B1, 1, 1%5D%5D%0A        System.out.println(prob.findSubsequences(new int%5B%5D%7B1, 2, 2%7D)); // %5B%5B1, 2%5D, %5B2, 2%5D, %5B1, 2, 2%5D%5D%0A        System.out.println(prob.findSubsequences(new int%5B%5D%7B4, 6, 7, 7%7D)); // %5B%5B4, 6%5D, %5B4, 7%5D, %5B4, 6, 7%5D, %5B4, 6, 7, 7%5D, %5B6, 7%5D, %5B6, 7, 7%5D, %5B7,7%5D, %5B4,7,7%5D%5D%0A        System.out.println(prob.findSubsequences(new int%5B%5D%7B4, 3, 2, 1%7D)); // %5B%5D%0A        System.out.println(prob.findSubsequences(new int%5B%5D%7B4, 3, 1, 2%7D)); // %5B%5B1, 2%5D%5D%0A        System.out.println(prob.findSubsequences(new int%5B%5D%7B4, 1, 3, 2%7D)); // %5B%5B1, 2%5D, %5B1, 3%5D%5D
+%7D%0A            %7D else %7B%0A                List%3CInteger%3E newAccu = new ArrayList%3C%3E();%0A                newAccu.add(nums.get(i));%0A                findSubsequences(nums, i + 1, newAccu, result);%0A            %7D%0A        %7D
 %0A   

Solve problem 491