Efficient DFS/Backtracking solution in Java

• Unlike a lot of other high vote solutions, my solution is much faster.
In terms of Big O, it is O(n^m) if target = n and candidates.length = m.
Not O(m^n)!!!

This is a big difference, let's say our target is 99, and there are 4 candidates.
My solution will run 99^4. Comparing to some other solutions, they require 4^99.

Please leave your comment below if you have any questions regarding my solution.

``````public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> solution = new ArrayList<List<Integer>>();
if (candidates == null || candidates.length == 0 || target <= 0) {
return solution;
}

List<Integer> set = new ArrayList<Integer>();
helper(set, candidates, target, 0, solution);
return solution;
}

private void helper(List<Integer> set, int[] candidates, int remaining, int level, List<List<Integer>> solution) {
// base case
if (level == candidates.length - 1) {
// trim the last level by directly compute how many numbers of the last candidate
// left in order to sum up to to the remaining target
if (remaining % candidates[level] == 0) {
int num = remaining / candidates[level];
for (int i = 0; i < num; i++) {
}
for (int i = 0; i < num; i++) {
set.remove(set.size() - 1);
}
return;
}
return;
}

// recursive rule
for (int i = 0; i <= remaining / candidates[level]; i++) {
for (int j = 0; j < i; j++) {
}
helper(set, candidates, remaining - i * candidates[level], level + 1, solution);
for (int j = 0; j < i; j++) {
if (set.size() > 0) {
set.remove(set.size() - 1);
}
}
}
}
}
``````

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