Java from 8th to 92th % by Checking Option Count


  • 0
    S

    The trick is pruning here:

    int options = max-place+1;
    if(options < (count-current.size())) return;

    Basically count up the number of remaining options vs. the number of numbers we need to reach the required count of values... If it's less then this branch cannot reach the end, so just cut it off.

        
        public List<List<Integer>> combine(int max, int count) {
            
            List<List<Integer>> tr = new ArrayList<List<Integer>>();
            
            compose(1, max, count, new ArrayList<Integer>(), tr);
            
            return tr;
            
        }
        
        void compose(int place, int max, int count, List<Integer> current, List<List<Integer>> tr){
            
            int options = max-place+1;
            
            if(options < (count-current.size())) return;
            
            if(current.size() == count){
                
                tr.add(current);
                
                return;
                
            }
            
            if(place > max) return;
                    
            compose(place+1, max, count, current, tr);
            
            List<Integer> clone = new ArrayList<Integer>(current);
            
            clone.add(place);
            
            compose (place+1, max, count, clone, tr);
            
        }
        
    }

Log in to reply
 

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