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


  • 0
    M

    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) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < a.length; i++) {
            if (target - a[i] < 0) continue;
            path.add(a[i]);
            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));
                current.add(single);
                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<>();        
                new_path.add(candidate);
                new_path.addAll(path);
                current.add(new_path);
            }
        }
        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. 
                    current.add(Arrays.asList(candidate));              
                    continue;
                }
                for (List<Integer> path : dp.get(sub - 1)) {    // subproblem is reused.
                    if (candidate > path.get(0)) continue;
                    List<Integer> new_path = new ArrayList<>();
                    new_path.add(candidate);
                    new_path.addAll(path);
                    current.add(new_path);
                }
            }
            dp.add(current);
        }
        return dp.get(target - 1);
    }
    

Log in to reply
 

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