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

• ``````	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);
for(int num: candidates) {
}

ArrayList<List<Integer>> initialCombosToTry =  new ArrayList<List<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) {
}

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) {
iter.remove();
}
}*/

List<List<Integer>> remainingCombos = new ArrayList<List<Integer>>();
for(List<Integer> combo : combosSoFar) {
int sumCombo = sumCombo(combo);
if(sumCombo == target)
//Discarding combos that are > target
else if(sumCombo < target) {
}
}
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) {
}
return cloned;
}

public <T> List<T> cloneAndAdd(List<T> list, T t) {
List<T> cloned =  cloneList(list);
return cloned;
//Use this code instead to see what happens if you don't clone your Lists.
//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) {
if(combo.isEmpty())