I'm having hard time understanding time complexity of my solution for combination sum problem. The problem is as follows:
Given a set of candidate numbers (
candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums totarget.The same repeated number may be chosen from candidates unlimited number of times.
Below is my solution written in Java using recursion:
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> results = new ArrayList<>();
recurse(results, candidates, target, 0, new ArrayList<>());
return results;
}
private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
if (target == 0) {
results.add(new ArrayList<>(acc));
return;
}
for (int i = idx; i < candidates.length; i++) {
if (candidates[i] > target) {
return;
}
acc.add(candidates[i]);
recurse(results, candidates, target - candidates[i], i, acc);
acc.remove(acc.size() - 1);
}
}
One can observe that the problem size of each recursive step is potentially not changed and the depth of the recursion is bound by target value e.g. if the candidates array contains number 1 the recursion will happen target times. If I simplify the code the interesting part is:
private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
if (target == 0) {
results.add(new ArrayList<>(acc));
return;
}
for (int i = idx; i < candidates.length; i++) {
acc.add(candidates[i]);
recurse(results, candidates, target - candidates[i], i, acc);
acc.remove(acc.size() - 1);
}
}
Which feels like O(candidates.length * target) for the most pessimistic candidates input with number 1.
Since my solution is not really a divide and conquer algorithm I guess that I can't apply the master theorem. It feels like a backtracking algorithm but I'm not familiar with finding upper bound for that type of algorithms.
Can someone please advise how to approach complexity analysis of above code?