public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<List<Integer>>();
getResult(result, new ArrayList<Integer>(), candidates, target, 0);
return result;
}
private void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){
if(target > 0){
for(int i = start; i < candidates.length && target >= candidates[i]; i++){
cur.add(candidates[i]);
getResult(result, cur, candidates, target  candidates[i], i);
cur.remove(cur.size()  1);
}//for
}//if
else if(target == 0 ){
result.add(new ArrayList<Integer>(cur));
}//else if
}
}
Java solution using recursive


From large to small might be easier and shorter.
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> result = new ArrayList<>(); dfs(result, new LinkedList<Integer>(), candidates, target); return result; } private void dfs(List<List<Integer>> result, LinkedList<Integer> list, int[] arr, int target) { if (target == 0) { result.add(new LinkedList<Integer>(list)); return; } for (int i = arr.length  1; i >= 0; i) { if (arr[i] <= target) { list.addFirst(arr[i]); dfs(result, list, Arrays.copyOfRange(arr, 0, i + 1), target  arr[i]); list.removeFirst(); } } } }

A little revise without using Arrays.sort which will run faster.
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); combinationSum(result,new ArrayList<Integer>(),candidates,target,0); return result; } public void combinationSum(List<List<Integer>> result, List<Integer> cur, int[] candidates, int target,int start) { if (target > 0) { for (int i = start;i < candidates.length;i++) { // not using the condition "target >= candidates[i]" cur.add(candidates[i]); combinationSum(result, cur, candidates, targetcandidates[i],i); cur.remove(cur.size()  1); } } if (target == 0) result.add(new ArrayList<Integer>(cur)); } }
I think we do not need to care about the order in the candidates. Please point out if I'm wrong.