AUG!!! Clean backtracking, 5ms. In JAVA with comment ,Let's discuss the time complexity of this method.


  • 1

    Hey guys, if the target is V, the minimum number of candidate is M, and the length of candidate is L, is the time complexity O(LlogL + V/M*L) ? Help me to figure this out, I appreciate it.

    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<>();
            if(candidates == null || candidates.length == 0)
                return result;
    //Key 1: sort the array in ascending order.
            Arrays.sort(candidates);
            List<Integer> currentCombination = new ArrayList<>();
            combinationSumBacktracker(result, candidates, 0, target, currentCombination);
            return result;
    
        }
        public void combinationSumBacktracker(List<List<Integer>> result, int[] candidates, int start, int target, List<Integer> previousCombination)
        {
    //Key 2: if start position is invalid or the first element is bigger than target.
    //then it is no need to continue. Since we sorted the array in ascending order        
            if(start >= candidates.length || candidates[start] > target)
                return;
            List<Integer> currentCombination = new ArrayList<>(previousCombination);
            for(int i = start ; i < candidates.length; i++)
            {
                currentCombination.add(candidates[i]);
                target -= candidates[i];
                if(0 == target)
                {
                    result.add(currentCombination);
                    return;
                }
    //Key 3, use i + 1 so that the next backtracking won't use the same element again.
    // if we use i for the next level, this method will the answer for problem 39! Cool !!!
                combinationSumBacktracker(result,candidates, i + 1, target, currentCombination);
                
                target +=candidates[i];
                currentCombination.remove(currentCombination.size() - 1);
    //Key 4, find the last position where its value is the same with the current one
                while(i + 1 < candidates.length && candidates[i + 1] == candidates[i])
                {
                    i++;
                }
            }
        }
    }
    

Log in to reply
 

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