Commented Solution with thinking process


  • 1

    Any suggestion is appreciated.

    /*
    This is a backtracking problem. 
    Brutal force is that we try every possible sequence.
    
    Since we need to avoid the repeating sequence, key of the optimization is to 
    somehow tell whether we have already include a list of integers in our result.
    
    To do this, we can either check with all the valid list we have so far everytime we want to put a new list
    or
    we need to come up with a good hashing function to hash a list to a number, then we only need to compare the hashcode everytime
    
    The way I come up with the hash code function below is that:
    You need a big prime number as factor, also want to take the incoming number and list size to be consideration,
    also you want to add a constant to it to handle all 0 case.
    
    I guess the most foolproof implememtation is to actual compare the list when the hashcode are the same.
    */
    
    public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            Set<Integer> hashCode = new HashSet<Integer>();
            //The sequence can start from every element in the array
            for(int i = 0; i < nums.length - 1; i++){
                List<Integer> current = new ArrayList<Integer>();
                helper(nums, current, result, i, hashCode, 0);
            }
            return result;
        }
        
        //Backtracking functino takes 6 parameters: input array, list valid list we put into result, final result,
        //index of the next number to try, hashcode of all the lists in the result, hashcode of last valid list.
        private void helper(int[] nums, List<Integer> list, List<List<Integer>> result, int index, Set<Integer> hashCode, int currentCode){
            if(index >= nums.length) return;
            if(list.isEmpty()){
                list.add(nums[index]);
                helper(nums,list,result,index ,hashCode, nums[index]);
            }else{
                for(int i = index+1; i < nums.length; i++){
                    //This is the hashcode formular.
                    int newCode = currentCode * 89 + nums[i] * (list.size() + 1) + 1;
                    //If current number is bigger than the last one in current sequence, 
                    //and the list we are about to add to result is not there yet, add it,
                    //then try to build more sequence based on that.
                    if(nums[i] >= list.get(list.size() - 1) && !hashCode.contains(newCode)){
                        List<Integer> element = new ArrayList<Integer>();
                        element.addAll(list);
                        element.add(nums[i]);
                        result.add(element);
                        hashCode.add(newCode);                
                        helper(nums, element, result, i, hashCode, newCode);
                    }
                }
            }
        }
    }

Log in to reply
 

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