Clean Java backtracking solution with HashSet to avoid duplicates


  • 0
    Y
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> result = new ArrayList();
            if(nums.length < 2) return result;
            helper(result, new ArrayList(), nums, 0);
            return result;
        }
        
        public void helper(List<List<Integer>> result, List<Integer> cur, int[] nums, int pos) {
            if(cur.size() > 1) {
                result.add(new ArrayList(cur));
            }
            HashSet<Integer> dup = new HashSet();
            int last = cur.size() > 0 ? cur.get(cur.size()-1) : Integer.MIN_VALUE;
            for(int i = pos; i < nums.length; i ++) {
                if(dup.contains(nums[i]) || nums[i] < last) continue;
                cur.add(nums[i]);
                dup.add(nums[i]);
                helper(result, cur, nums, i+1);
                cur.remove(cur.size()-1);
            }
        }
    

Log in to reply
 

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