My DFS and backtracking Java solution


  • 0
    J

    public int numSquares(int n) {

        int len = (int) Math.sqrt((double) n);
        
        int[] nums = new int[len+1];
        
        for (int i = 1; i <= len; i++) {
            nums[i] = i * i;
        }
        
        int result = 0;
        int min = Integer.MAX_VALUE;
        List<Integer> res = new ArrayList<Integer>();
        
        for (int i = len; i >= 1; i--) {
        	int temp = helper(nums, i, min, res, n);
        	
        	if (min > temp)
        		min = temp;
        }
        
        return min;
    }
    
    private int helper(int[] nums, int end, int min, List<Integer> res, int target) {
        while (end >= 1) {
            	int step = 0;
            	
            	if (target == 0)
            		return min;
            	
            	res.add(nums[end]);
            	target = target - nums[end];
            	
            	
            	
            	if (res.size() >= min) {
            		int temp = res.remove(res.size()-1);
            		target += temp;
            		break;
            	}
            
    	        if (target == 0) {
    	        	if (res.size() < min) {
    	        		min = res.size();
    	        		
    	        	}
    	        }
    	        
    	        if (target > 0) {
    		        if (target >= nums[end])
    		            min = helper(nums, end, min, res, target);
    		        else {
    		            
    		        	while (nums[end-1] > target) {
    		        		end--;
    		        		
    		        		// backtrack the steps jumped
    		        		step++;
    		        	}
    		        	
    		            min = helper(nums, end-1, min, res, target);
    		            
    		        }
    	        }
    	        
    	        // restore the target value
    	        int temp = res.remove(res.size()-1).intValue();
    	        target += temp;
    	        
    	        // if the first element value has been deducted from target in the main function, we may not need this step
    	        
    	        if (res.size() == 0)
    	        	break;
    	        
    	        end--;
    	        end += step;
    	        
        }
            
            
        return min;
            
        
    }

Log in to reply
 

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