Efficient DFS/Backtracking solution in Java


  • 0
    W

    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++) {
                        set.add(candidates[level]);
                    }
                    solution.add(new ArrayList(set));
                    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++) {
                    set.add(candidates[level]);
                }
                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);
                    }
                }
            }
        }
    }
    

Log in to reply
 

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