Java backtracking solution, beats 100% with explaination


  • 0

    The main challenge here is to remove duplicates. We can use a set in the findSubsequence method and traverse the res list, but it is not efficient. I use a hash set in the helper method instead. Every time if a number "n" has already been visited in this method(which means we have already got all of the results who start with "n"), we will ignore the following "n".

    hope it helps

    public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(nums == null || nums.length == 0) {
                return res;
            }
            List<Integer> path = new ArrayList<Integer>();
            helper(nums, res, path, 0);
            return res;
        }
        
        protected void helper(int[] nums, List<List<Integer>> res, List<Integer> path, int start) {
            if(nums == null || nums.length == 0) {
                return;
            }
            if(path.size() >= 2) {
                res.add(new ArrayList<Integer>(path));
            }
            HashSet<Integer> set = new HashSet<Integer>(); 
            for(int i = start; i < nums.length; i++) {
                if(path.size() == 0 || nums[i] >= path.get(path.size()-1)) {
                    if(set.add(nums[i])) {
                        path.add(nums[i]);
                        helper(nums, res, path, i+1);
                        path.remove(path.size()-1);
                    }
                }
            }
        }
    }

Log in to reply
 

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