Java solution beats 100%


  • 19
    public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> res = new LinkedList<>();
            helper(new LinkedList<Integer>(), 0, nums, res);
            return res; 
        }
        private void helper(LinkedList<Integer> list, int index, int[] nums, List<List<Integer>> res){
            if(list.size()>1) res.add(new LinkedList<Integer>(list));
            Set<Integer> used = new HashSet<>();
            for(int i = index; i<nums.length; i++){
                if(used.contains(nums[i])) continue;
                if(list.size()==0 || nums[i]>=list.peekLast()){
                    used.add(nums[i]);
                    list.add(nums[i]); 
                    helper(list, i+1, nums, res);
                    list.remove(list.size()-1);
                }
            }
        }
    }
    

    Pretty straightforward. Maybe one thing is: while nums is not necessarily sorted but we have to skip duplicates in each recursion, so we use a hash set to record what we have used in this particular recursion.


  • 0
    P
    public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> rst = new ArrayList<>();
            if (nums == null || nums.length == 0){
                return rst;
            }    
            dfs(rst, new ArrayList<Integer>(), 0, nums, -101);
            return rst;
        }
        
        private void dfs(List<List<Integer>> rst, List<Integer> path , int idx, int[] nums,int pre){
            if (path.size() >= 2){
                rst.add(new ArrayList(path));
            }
            if (idx == nums.length){
                return;
            }
            Set<Integer> set = new HashSet<>();
            for (int i = idx; i < nums.length; i++){
                if (set.contains(nums[i])){
                    continue;
                }
                set.add(nums[i]);
                if (nums[i] >= pre){
                    path.add(nums[i]);
                    dfs(rst, path, i + 1, nums, nums[i]);
                    path.remove(path.size() - 1);
                }
            }
        }
    

    because you know the range of integer, can pass the previous value in recursive function instead of get the last element in arraylist.


  • 0

    @payphonepfgmail.com Yes, make sense. Using LinkedList.peekLast() is still O(1) though. Doesn't really make much difference.


  • 1
    J

    How to analyze the runtime and space complexity for this?


  • 0
    G

    Nice solution and it runs really fast.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.