491. Increasing Subsequences.md

491. Increasing Subsequences

---

leetcode-cn Daily Challenge on August 25th, 2020.

---

Difficulty : Medium

Related Topics : DFS

---

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]]

Constraints:

• 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.

---

Solution

• mine
  • Java
    • BFS Runtime: 16 ms, faster than 48.35%, Memory Usage: 54 MB, less than 44.85% of Java online submissions

      public List<List<Integer>> findSubsequences(int[] nums) {
          int n = nums.length;
          List<List<Integer>> res = new LinkedList<>();
          //record index
          LinkedList<LinkedList<Integer>> list = new LinkedList<>();
          //record has added value in each loop
          Set<Integer> set = new HashSet<>();
      
          for (int i = 0; i < n - 1; i++) {
              if (set.contains(nums[i])) continue;
              set.add(nums[i]);
              list.add(new LinkedList<>(Arrays.asList(i)));
          }
          while (!list.isEmpty()) {
              set.clear();
              //get the first checked index list
              LinkedList<Integer> t = list.removeFirst();
              if (t.size() > 1) {
                  //at least 2
                  LinkedList<Integer> r = new LinkedList<>();
                  for (int i : t) {
                      r.add(nums[i]);
                  }
                  res.add(r);
              }
              //get last index
              int end = t.getLast();
              for (int i = end + 1; i < n; i++) {
                  //skip lower than nums[end] and  if we had added in this loop
                  if (nums[i] < nums[end] || set.contains(nums[i])) continue;
      
                  set.add(nums[i]);
                  LinkedList<Integer> next = new LinkedList<>(t);
                  next.add(i);
                  list.add(next);
              }
          }
          return res;
      }
      

---

• the most votes

• Runtime: 2 ms, faster than 100.00%, Memory Usage: 45.1 MB, less than 99.17% of Java online submissions

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

---