5ms AC solution, easy to understand


  • -1
    Y

    This is not easy for me, so I read this artical first:
    http://www.programcreek.com/2014/03/leetcode-combinations-java/ and do a little bit change then conquer this problem with 5ms runtime.

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(n <=3) return res;
        List<Integer> item = new ArrayList();
        getAllFactors(n, item, res);
        return res;
    }
    
    public void getAllFactors(int n, List<Integer> item, List<List<Integer>> res){
        if(n <= 3) {
        	return;
        }
        for(int i= 2; i*i<= n; i++){
            if(item.size() == 0 
                ||
                item.size() > 0 && item.get(item.size()-1) <= i)
            {
            	if((n % i == 0)){
                    List<Integer> l = new ArrayList(item);
                    //if n%i == 0, like 16%2 ==0 ,then put 2, 8 into list
                    l.add(i);l.add(n/i); 
                    res.add(l);
                    
                    item.add(i);     
                    getAllFactors(n/i, item,res);                 
                    item.remove(item.size()-1);
            	}
    
            }
        }
    }

Log in to reply
 

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