leetcode491-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:**

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.

现有一个无序的整数数组，要求找到所有递增的子序列。

思路和代码

这里采用深度优先的思路进行解决。先将数组按照从小到大排序，再从左往右遍历数组，每个数字有两种可能，分别是选中到子数组，或者不选中。将所有的结果收纳即可获得最终的结果集。

但是这里存在一个去重问题，如 [1,7,7] 这样的数组，按照上面的规则会生成如下的子序列[1,7], [1,7], [1,7,7]。因此在每一轮选择的时候，都需要判断一下该数字在这一轮是否已经被选中过了。在一个有序的数组中

其实按照规则来说，即使不将整数数组进行排序也是可以实现的。因为记录的每个当前的 subsequence 都是按照从小到大的递增子序列，只要判断当前的数字是否比递增子序列大就可以了。

代码如下：

    public List<List<Integer>> findSubsequences(int[] nums) {List<List<Integer>> result = new ArrayList<>();
        findSubsequences(nums, new LinkedList<>(), 0, result);
        return result;
    }

    public void findSubsequences(int[] nums, LinkedList<Integer> subSequence, int startIndex, List<List<Integer>> result) {if (subSequence.size() >= 2) {result.add(new LinkedList<>(subSequence));
        }
        Set<Integer> used = new HashSet<>();
        for (int i = startIndex ; i<nums.length ; i++) {if (used.contains(nums[i])) {continue;}
            if (subSequence.size() == 0 || nums[i] >= subSequence.peekLast()) {used.add(nums[i]);
                subSequence.add(nums[i]);
                findSubsequences(nums, subSequence, i+1, result);
                subSequence.removeLast();}

        }
    }