No iteration Java Solution,only recursive


  • 0
    D
    	public List<List<Integer>> combinationSum( int[] candidates, int target ) {
    		List<List<Integer>> result = new ArrayList<List<Integer>>();
    		List<Integer> subResult = null;
    		subResult = new ArrayList<Integer>();
    		recurive( subResult, candidates, candidates.length - 1, target, result, 0 );
    		return result;
    	}
    
    	private void recurive( List<Integer> subResult, int[] candidates, int start, int target, List<List<Integer>> result, int subSum ) {
    
    		int s = subSum;
    
    		if( start < 0 || s > target ) {
    			return;
    		}
    
    		List<Integer> sList = new ArrayList<>( subResult );
    
    		if( s == target ) {
    			result.add( sList );
    			return;
    		}
    
    		sList.add( candidates[ start ] );
    
    		s += candidates[ start ];
    
    		recurive( sList, candidates, start, target, result, s );
    
    		int size = sList.size();
    
    		if( size > 0 ) {
    			s -= sList.get( size - 1 );
    			sList.remove( size - 1 );
    		}
    
    		if( start - 1 >= 0 ) {	
    			recurive( sList, candidates, --start, target, result, s );
    		}
    
    	}
    

Log in to reply
 

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