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.
类似combination,也可以用back tracking来做
class Solution { public List<List<Integer>> findSubsequences(int[] nums) { Set<List<Integer>> rt = new HashSet<>(); helper(rt, nums, 0, new ArrayList<>()); List<List<Integer>> r = new ArrayList<>(); r.addAll(rt); return r; } private void helper(Set<List<Integer>> rt, int[] nums, int i, List<Integer> cur) { if (i == nums.length) { if (cur.size() > 1) rt.add(cur); return; } if (cur.isEmpty() || nums[i] >= cur.get(cur.size() - 1)) { List<Integer> list = new ArrayList<>(cur); list.add(nums[i]); helper(rt, nums, i + 1, list); } helper(rt, nums, i + 1, cur); } }
No comments:
Post a Comment