美文网首页
Increasing Subsequences

Increasing Subsequences

作者: Frank_Kivi | 来源:发表于2018-06-28 11:10 被阅读4次

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);
            }
        }
    }
}

相关文章

网友评论

      本文标题:Increasing Subsequences

      本文链接:https://www.haomeiwen.com/subject/chhgyftx.html