https://www.lintcode.com/problem/increasing-subsequences/description
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
/**
* @param nums: an integer array
* @return: all the different possible increasing subsequences of the given array
*/
public List<List<Integer>> findSubsequences(int[] nums) {
// Write your code here
Set<List<Integer>> set = new HashSet<>();
treeWalk(nums, 0, set, new ArrayList<Integer>());
return new ArrayList<List<Integer>>(set);
}
private void treeWalk(int[] nums, int i, Set<List<Integer>> set, ArrayList<Integer> integers) {
if (integers.size() > 1) {
set.add(new ArrayList<Integer>(integers));
}
for (int j = i; j < nums.length; j++) {
if (integers.isEmpty() || integers.get(integers.size() - 1) <= nums[j]) {
integers.add(nums[j]);
treeWalk(nums, j + 1, set, integers);
integers.remove(integers.size() - 1);
}
}
}
}
网友评论