Java 20 lines backtracking solution using set, beats 100%.


  • 31
    A
    public class Solution {
    
         public List<List<Integer>> findSubsequences(int[] nums) {
             Set<List<Integer>> res= new HashSet<List<Integer>>();
             List<Integer> holder = new ArrayList<Integer>();
             findSequence(res, holder, 0, nums);
             List result = new ArrayList(res);
             return result;
         }
    
        public void findSequence(Set<List<Integer>> res, List<Integer> holder, int index, int[] nums) {
            if (holder.size() >= 2) {
                res.add(new ArrayList(holder));
            }
            for (int i = index; i < nums.length; i++) {
                if(holder.size() == 0 || holder.get(holder.size() - 1) <= nums[i]) {
                    holder.add(nums[i]);
                    findSequence(res, holder, i + 1, nums);
                    holder.remove(holder.size() - 1);
                }
            }
        }
    }

  • 0
    M

    Thanks for sharing. I have very similar idea to yours, it's just I don't use a Set to avoid duplicated result, but my code cannot pass a long case ( [1,2,3,4,5,6,7,8,9,10,1,1,1,1,1] ), I have no idea about the problem. Any suggestions?

    public class Solution {
        private void helper(int[] nums, int index, List<Integer> buffer, List<List<Integer>> result){
            if( buffer.size()>=2 )
                result.add( new ArrayList<Integer>(buffer) ); 
                
            for(int i=index; i<nums.length; i++){
                if( buffer.size()==0 || nums[i]>=buffer.get(buffer.size()-1) ){
                    buffer.add(nums[i]);
                    helper(nums, i+1, buffer, result); 
                    buffer.remove(buffer.size()-1); 
                }
                
                while(i+1<nums.length && nums[i]==nums[i+1])
                    i++;
            }
        }
        
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>(); 
            if(nums.length<2)
                return result; 
            
            helper(nums, 0, new ArrayList<Integer>(), result);
            return result;
        }
    }
    

  • 4
    A

    @mycoy
    I tried with smaller input i.e. [1,2,3,2] and your code fails, it adds duplicate.
    your output : [[1,2],[1,2,3],[1,2,2],[1,3],[1,2],[2,3],[2,2]]
    Expected : [[1,2],[2,2],[1,3],[2,3],[1,2,3],[1,2,2]]

    In yours [1,2] is repeated twice and to avoid this I have maintained a set.

    With the while loop you are just checking if consecutive elements are same. If the test case is [1,2,2,3] your logic will work, but it will not when the repeated elements is not consecutive.


  • 1
    M

    @adarshkp said in Java 20 lines backtracking solution using set, beats 100%.:

    [1,2,3,2]

    Thanks for pointing out my problem. You're correct, my code cannot handle cases like, [1,2,3,2]; I didn't understand that point well.


  • 0

    @adarshkp

    Thanks for sharing. Didn't expect backtracking can run this fast.


  • 0

    @mycoy we cannot use Arrays.sort() (according to the probelm), so the same elements are not gathered togather(adjacent), so we cannot use "if(i != index && array[i-1] == array[i]) continue;" to deduplicate


  • 0
    T

    What is the time complexity of this algorithm? Is it 2n ?


  • 0

    Thank you very much! It is easy to understand.


  • 0

    Thanks for sharing! I also have similar idea, but I am still look for solution that does not use hashset to avoid duplicates. Does anyone have some idea?

    public List<List<Integer>> findSubsequences(int[] nums) {
            Set<List<Integer>> res = new HashSet<List<Integer>>();
            for(int i = 0; i < nums.length - 1; i ++){
                dfs(res, new ArrayList<Integer>(), nums, i, Integer.MIN_VALUE);
            }
            return new ArrayList(res);
        }
        public void dfs(Set<List<Integer>> res, List<Integer> cur, int[] nums, int start, int pre){
            if(cur.size() > 1){
                res.add(new ArrayList<Integer>(cur));
            }
            for(int i = start; i < nums.length; i ++){
                if(nums[i] < pre) continue;
                cur.add(nums[i]);
                int tmp = pre;
                dfs(res, cur, nums, i + 1, nums[i]);
                pre = tmp;
                cur.remove(cur.size() - 1);
            }
        }
    

  • 0
    R

    @mycoy Because input array is not sorted, you way to avoid duplication is only working for sorted array.


  • 0

    @mycoy even using arraylist.contains() method to avoid the duplicate elements, you will still get a time limit error. my suggest is using a set instead, it only takesO (1) to check the repeated element


  • 1

    Thanks for sharing! This problem is similar to Subset II. So at first it seems same techniques ("Arrays.sort(nums)" first then bypass duplicate by "i > start && nums[i] == nums[i-1]") could be in use. Then I realize that I miss the key requirement of this problem: subsequence which means we cannot change original array. Then Set seems to be the only thing to resort.


  • 0
    F

    have to say.... your variable naming skill is just tremendous! well-understood by aliens from lala galaxy...


  • 0
    Y

    Same idea, a slight difference is pass the min value for the next recursive call instead of using the last element in path.

    public class Solution {
        Set<List<Integer>> ans = new HashSet<>();
    
        public List<List<Integer>> findSubsequences(int[] nums) {
            helper(nums, 0, Integer.MIN_VALUE, new ArrayList<Integer>());
            return new ArrayList<List<Integer>>(ans);
        }
    
        public void helper(int[] nums, int idx, int min, ArrayList<Integer> path) {
            if (path.size() >= 2) {
                ans.add(new ArrayList<Integer>(path));
            }
    
            for (int i = idx; i < nums.length; ++i) {
                if (nums[i] >= min) {
                    path.add(nums[i]);
                    helper(nums, i + 1, nums[i], path);
                    path.remove(path.size() - 1);
                }
            }
        }
    }
    

  • 0
    F
    This post is deleted!

  • 0
    V
    This post is deleted!

  • 0
    J

    @adarshkp
    I used set to store popped items instead of sets. I think it is slightly more efficient.
    void findHelper(vector<int>& tmp, int i, vector<vector<int>>& res, vector<int>& nums) {

    if (tmp.size() > 1)
        res.push_back(tmp);
    
    unordered_set<int> popped;
    
    for (int j = i; j < nums.size(); j++) {
    
        if (!tmp.empty() && tmp.back() > nums[j])
            continue;
    
        if(popped.find(nums[j]) != popped.end())
            continue;
    
        tmp.push_back(nums[j]);
    
        findHelper(tmp, j + 1, res, nums);
    
        tmp.pop_back();
    
        popped.insert(nums[j]);
    }
    

    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {

    vector<int> tmp;
    vector<vector<int>> res;
    findHelper(tmp, 0, res, nums);
    return res;
    

    }


  • 1
    S

    A possible improvement: instead of using a global set to remove duplication in the final results, we can maintain a local set at each step. The principle is that at each step, a new value can only be picked once.

    The advantage of a local set is that it can filter out the potential repetitions just at the beginning instead of at the end of a sub-sequence building. For example, [1, 1, 9, 3, 6]. With a global set, we have to filter all the sequences starting at the 2nd 1 since they will certainly duplicate with the results beginning with the 1st 1. However, with a local set, at the first step, we will only choose the 1st 1 for sequence building and the 2nd 1 is excluded just at the first step.

    Of course a local set at each step will lead to extra costs. However, I think it can improve the efficiency in general, especially for an array with many repetitions, such as [1, 1, 1, 1, 1, 1, 3].

    class Solution(object):
        def findSubsequences(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            self.r = []
            self.path = []
            self.nums = nums
            self.backtrack(0)
            return self.r
            
        def backtrack(self, i):
            # choose next number starting from the index i
            if i == len(self.nums):
                return
            # for j in index range [i, len), if nums[j] >= last in the 
            # path and its value has not been used at this step, then use it
            s = set()   # check possible repetitions of this step
            for j in range(i, len(self.nums)):
                if (not self.path or self.nums[j] >= self.path[-1]) and (self.nums[j] not in s):
                    s.add(self.nums[j])
                    self.path.append(self.nums[j]) # a new value is appended
                    if len(self.path) >= 2:
                        self.r.append(list(self.path))
                    self.backtrack(j + 1)
                    del self.path[-1] # restore the state

  • 0
    C

    I still has one problem : will this problem output repetitive calculation. eg. [4,6,6,7] we begin at 4 and check 6 7 but when the loop begins at 6 we go through the same path
    How to optimize it I think of using the hashMap but I can't write the code


  • 0
    X
    This post is deleted!

Log in to reply
 

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