# Backtracking / Top-Down DP / Bottom-Up DP solutions in Java

• Solution 1: Backtracking

``````List<List<Integer>> combSum_BK(int[] a, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(a, target, result, new ArrayList<>(), 0);
return result;
}

void backtrack(int[] a, int target, List<List<Integer>> result, List<Integer> path, int start) {
if (target == 0) {
return;
}
for (int i = start; i < a.length; i++) {
if (target - a[i] < 0) continue;
backtrack(a, target - a[i], result, path, i);
path.remove(path.size() - 1);
}
}
``````

Solution 2: Top-Down DP

``````List<List<Integer>> combSum_DP_TopDown(int[] a, int target) {
List<List<List<Integer>>> dp = new ArrayList<>(target);
Arrays.sort(a);
for (int i = 0; i <= target; i++) dp.add(null);
return subProblem(a, target, dp);
}

List<List<Integer>> subProblem(int[] a, int target, List<List<List<Integer>>> dp) {
if (dp.get(target) != null) return dp.get(target);  // Already calculated. Reuse.
List<List<Integer>> current = new ArrayList<>();    // Not yet calculated.
for (int candidate : a) {
if (target - candidate < 0) break;      // Subproblem doesn't exist.
if (target - candidate == 0) {          // Subproblem is candidate itself.
List<Integer> single = new ArrayList<>(Arrays.asList(candidate));
continue;
}
List<List<Integer>> old = subProblem(a, target - candidate, dp); //check Subproblem
for (List<Integer> path : old) {            // Add candidate to all results.
if (candidate > path.get(0)) continue;
List<Integer> new_path = new ArrayList<>();
}
}
dp.set(target, current);    // Current problem results memoized.
return dp.get(target);
}
``````

Solution 3: Bottom-Up DP

``````List<List<Integer>> comb_DP_BottomUp(int[] a, int target) {
Arrays.sort(a);
List<List<List<Integer>>> dp = new ArrayList<>();
for (int i = 1; i <= target; i++) {
List<List<Integer>> current = new ArrayList<>();
for (int candidate : a) {
int sub = i - candidate;
if (sub < 0) break;         // subproblem doesn't exist.
if (sub == 0) {             // subproblem is candidate itself.
continue;
}
for (List<Integer> path : dp.get(sub - 1)) {    // subproblem is reused.
if (candidate > path.get(0)) continue;
List<Integer> new_path = new ArrayList<>();