# Simple and fast DFS solution, python AC 98ms

• ``````class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
candidates.sort()
stack = [(0, 0, [])]
result = []
while stack:
total, start, res = stack.pop()
if total == target:
result.append(res)
for n in range(start, len(candidates)):
t = total + candidates[n]
if t > target:
break
stack.append((t, n, res + [candidates[n]]))
return result
``````

JAVA

``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>();
Stack<Integer> sum = new Stack<Integer>();
Stack<Integer> start = new Stack<Integer>();
stack.push(new ArrayList<Integer>());
sum.push(0);
start.push(0);
List<List<Integer>> result = new ArrayList<List<Integer>>();
while (!stack.isEmpty()) {
List<Integer> res = stack.pop();
int total = sum.pop();
int begin = start.pop();
if (total == target)
else {
for (int i = begin; i < candidates.length; i++) {
int t = total + candidates[i];
if (t > target)
break;
ArrayList<Integer> r = new ArrayList<Integer>(res);