Intuitive Java Recursive Solution


  • 0

    I found the top solution is not so intuitive, which I had hard time understanding, so here I come up with a easy understanding solution. For each index k, we already get previous k-1's solution, so it is building up the results recursively.

        private Set<List<Integer>> helper(int[] nums, int k) {
            Set<List<Integer>> res = new HashSet<>();
            if(k<=0)
                return res;
    
            for(int i=0; i<k; i++) {
                if(nums[i]<=nums[k]) {
                    List<Integer> lst = new ArrayList<>();
                    lst.add(nums[i]);
                    lst.add(nums[k]);
                    res.add(lst);
                }
            }
            
            Set<List<Integer>> subRes = helper(nums, k-1);
            for(List<Integer> subLst : subRes) {
                if(nums[k] >= subLst.get(subLst.size()-1)) {
                    List<Integer> newSubLst = new ArrayList<>();
                    newSubLst.addAll(subLst);
                    newSubLst.add(nums[k]);
                    res.add(newSubLst);
                }
                res.add(subLst);
            }
            
            return res;
        }
        
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            res.addAll(helper(nums, nums.length-1));
            return res;
        }

Log in to reply
 

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