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

• 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++)
{
target -= candidates[i];
if(0 == target)
{
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++;
}
}
}
}

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