0
$\begingroup$

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 to target.

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?

$\endgroup$
0
$\begingroup$

The obvious algorithm tries all subsets, i.e., is $O(2^n)$ if you have $n$ elements to select. And your algorithm does that (try with first element, try without first element).

Complexity is given by the recurrence:

$$T(n) = 2 T(n - 1), T(0) \text{ given}$$

(try two posibilities for first one, recurse on the $n - 1$ others for each).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.