Here's an accepted solution for Combination Sum-- it contains many useful tricks


  • 0
    G
    	public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
    		//Sorting and removing duplicates is a good start, since we're required to return our
    		//combinations in non-descending order, and since duplicates are not allowed.
    		//The expand method below also works to prevent duplicates.
    		Arrays.sort(candidates);
    		LinkedHashSet<Integer> distinctOrderedCandidates = new LinkedHashSet<Integer>();
    		for(int num: candidates) {
    			distinctOrderedCandidates.add(num); 
    		}
    
    		ArrayList<List<Integer>> initialCombosToTry =  new ArrayList<List<Integer>>();
    		initialCombosToTry.add(new ArrayList<Integer>());
    		ArrayList<List<Integer>> allCombinations = new ArrayList<List<Integer>>();
    		combinationSum(allCombinations, initialCombosToTry , distinctOrderedCandidates, target);
    
    	//ArrayList<ArrayList<Integer>> is a signature that would not do well for you in a tech interview.
    	//LeetCode should stop using that signature.
    	//A List<List<Integer>> maximizes the number of methods you can pass the structure to.
    	//Fortunately the performance cost of converting to the required signature is negligible.
    		ArrayList<ArrayList<Integer>> obeyTheRequiredSignature = new ArrayList<ArrayList<Integer>>();
    		for(List<Integer> combo : allCombinations) {
    			obeyTheRequiredSignature.add( (ArrayList) combo);
    		}
    		
            return obeyTheRequiredSignature;
    	}
    	
        //Doing a breadth first search. This method is tail recursive, and therefore, if done in a language like Scala would be
    	//optimized so that it would never cause a stack overflow for any input.  However, the combosSoFar list grows quickly,
    	//and so an out-of-memory error would still quite possible with this algorithm.
    	public void combinationSum(List<List<Integer>> successes, List<List<Integer>> combosSoFar, LinkedHashSet<Integer> elements, int target) {
    		//System.out.println("combosSoFar.size == " + combosSoFar.size());
    		if(combosSoFar.isEmpty())
    			return;
    		//I tried a ListIterator so that we can remove in place rather than creating a new List here. 
    		//I thought that might speed things up, but the ListIterator.remove must be way slower than
    		//simply creating a new List and adding to it, because doing the latter made time on a long
    		//combination go from 649 milliseoncds to 146 milliseconds.
    /*		for(Iterator<List<Integer>> iter = combosSoFar.listIterator(); iter.hasNext(); ) {
    			List<Integer> combo = iter.next();
    			int sumCombo = sumCombo(combo);
    			if(sumCombo > target)
    				iter.remove();
    			else if(sumCombo == target) {
    				successes.add(combo);
    				iter.remove();
    			}    
    		}*/
    		
    		List<List<Integer>> remainingCombos = new ArrayList<List<Integer>>();
    		for(List<Integer> combo : combosSoFar) {
    			int sumCombo = sumCombo(combo);
    			if(sumCombo == target)
    				successes.add(combo);
    			//Discarding combos that are > target
    			else if(sumCombo < target) {
    				remainingCombos.add(combo);
    			}
    		}
    		combinationSum(successes, expand(remainingCombos, elements), elements, target);   
    	}
    	public int sumCombo(List<Integer> nums) {
    		int sum = 0;
    		for(Integer num: nums) {
    			sum += num;
    		}
    		return sum;
    	}	
    	public <T> List<T> cloneList(List<T> list) {
    		List<T> cloned = new ArrayList<T>();
    		for(T t : list) {
    			cloned.add(t);
    		}
    		return cloned;
    	}		
    	
    	public <T> List<T> cloneAndAdd(List<T> list, T t) {
    		List<T> cloned =  cloneList(list);
    		cloned.add(t);
    		return cloned;
    		//Use this code instead to see what happens if you don't clone your Lists.
    		//list.add(t);
    		//return list;
    	}
    	
    	private List<List<Integer>> expand(List<List<Integer>> combosSoFar, LinkedHashSet<Integer> elements) {
    		List<List<Integer>> expanded = new ArrayList<List<Integer>>();
    		//When expanding, the element added must be >= the last element in the combo, unless the combo is empty.
    		//Also, we need to clone our combo List, otherwise we'd have one combo list that gets many many pathElements to it
    		//rather than having many combo lists that get one of each path element added.
    		for(List<Integer> combo : combosSoFar) {
    			for(Integer pathElementToAdd : elements) {
    				if(combo.isEmpty())
    					expanded.add(cloneAndAdd(combo, pathElementToAdd));
    				else {
    					if(pathElementToAdd >= combo.get(combo.size() - 1)) {
    						expanded.add(cloneAndAdd(combo, pathElementToAdd));
    					}
    				}          
    			}
    		}
    		return expanded;
    	}

Log in to reply
 

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