Skip to content

Instantly share code, notes, and snippets.

@b27lu
Created February 12, 2014 16:19
Show Gist options
  • Save b27lu/8958815 to your computer and use it in GitHub Desktop.
Save b27lu/8958815 to your computer and use it in GitHub Desktop.
Combination Sum LeetCode
public class Solution {
public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
if(candidates == null)
return null;
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
if(target <= 0)
return result;
Arrays.sort(candidates);
//currentSum and position are all 0
dfsWorker(candidates, target, result, temp, 0, 0);
return result;
}
public void dfsWorker(int[] candidates, int target, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp, int currentSum, int position){
//currentSum reachs target, add the current sequence to result
if(currentSum == target){
result.add(new ArrayList<Integer>(temp));
return;
}
if(currentSum > target)
return;
for(int i = position;i<candidates.length;i++){
//only no greater than target element will be considered
if(candidates[i] <= target){
temp.add(candidates[i]);
//since same number can be used more than once, the position is still "i" in arguments
dfsWorker(candidates, target, result, temp, candidates[i]+currentSum, i);
temp.remove(temp.size()-1);
//skip duplicate elements
while(i < candidates.length - 1 && candidates[i] == candidates[i+1])
i++;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment