1
$\begingroup$

I have the following problem:

Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array for implementation of the set. What is the time complexity?

I have already solved the problem, both the idea and the C code is given below. My questions are:

  1. How do I calculate the time complexity of my solution?
  2. Is there a better way to solve this problem?

My idea:

The function f takes a, n, p, and furthermore a variable idx for the current index in the array, and a boolean array subset which marks which elements in a are in the subset considered by this iteration of f.

First we iterate through subset and for each element in a currently in the subset, we multiply it by the product variable (initialized to 1).

If at any point during this iteration the product equals p we print out the elements in subset.

However if at any point the product becomes larger than p we return immediately. No further multiplication by positive integers could possibly bring the product down.

If the product is less than or equal to p after the iteration is done, we iterate through each of the elements in a, after and including idx, for each making a copy of subset, adding the element to it and calling the function recursively for the next idx and the copy of subset.

We have to do this even if the product is equal to p because I cannot assume the set is sorted; there may be a 1 down the road which would also give a result of p if added to the current subset.

What this means is that the function, called initially with an empty subset and idx of 0, will evaluate the possible subsets in the following order:

{}
{ 0 }
{ 0, 1 }
{ 0, 1, 2 }
..
{ 0, 1, 2 .. n-1 }
{ 0, 1, 2 .. n-1, n }
{ 0, 1, 2 .. n-2, n }
{ 0, 1, 2 .. n-3, n-1 }
{ 0, 1, 2 .. n-3, n-1, n }
{ 0, 1, 2 .. n-3, n }
{ 0, 1, 2 .. n-4, n-2 }
{ 0, 1, 2 .. n-4, n-2, n-1 }
{ 0, 1, 2 .. n-4, n-2, n-1, n }
{ 0, 1, 2 .. n-4, n-2, n }
{ 0, 1, 2 .. n-4, n-1 }
{ 0, 1, 2 .. n-4, n-1, n }
{ 0, 1, 2 .. n-4, n }
..
{ 0, 2 }
{ 0, 2, 3 }
..
{ 1 }
{ 1, 2 }
..

And so on, you get the picture.

Time complexity?

I found both my idea and code too tough for trying to deduce the time complexity from, so I the first thought was that the time complexity must be $O(2^n)$ because it goes through all the $2^n$ subsets.

However, it doesn't go through all of them. If it detects a subset s the product of whose elements exceeds p, it immediately rejects both s and all other subsets of a that also have the offending s as a subset.

Does this impact the big O class, and if so, how? A rule of thumb I could apply to similar problems would be preferable to me instead of (or in addition to) any hard-to-digest theory.

The code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void
f(
    unsigned *a,
    int n,
    int idx,
    unsigned p,
    bool *subset
)
{
    unsigned product = 1;
    bool empty_subset = true;

    for(int i=0; i<n; i++) {
        if(subset[i] == true) {
            product *= a[i];
            empty_subset = false;
        }

        if(product > p)
            return;
    }

    if(product == p && !empty_subset) {
        for(int i=0; i<n; i++)
            if(subset[i])
                printf("%u, ",a[i]);
        printf("\n");
    }

    if(idx >= n) return;

    for(int i=idx; i<n; i++) {
        bool *newsubset = (bool*)malloc(sizeof(bool) * n);
        for(int j=0; j<n; j++)
            newsubset[j] = subset[j];

        newsubset[idx] = true;

        f(a, n, ++idx, p, newsubset);

        free(newsubset);
    }
}
$\endgroup$
0
$\begingroup$

Suppose the set is

$$a = \{2,3,6\} \cup \{5,7,35\} \cup \{11,13,143\} \cup \{17,19,323\} \cup \cdots \cup \{p_{2k-1},p_{2k},p_{2k-1}p_{2k}\}.$$

(Do you see the pattern? It has $3k$ elements, composed of $k$ groups of three. The $i$th group contains $p_{2i-1}$, the $2i-1$th prime, and $p_{2i}$, the $2i$-th prime, and their product.)

Also, suppose the product you want to hit is $p=p_1p_2 \cdots p_{2k}$.

Then this set has at least $2^k$ subsets that multiply to this value. In particular, in each group, you can either pick the first two terms, or you can pick the third term.

So you'll need to output at least $2^k$ sets. This means the running time on an input of size $3k$ can be as large as $2^k$. Or, in other words, the running time on an input of size $n$ can be as large as $2^{n/3}$. This is exponential in the length of the input. Therefore, the worst-case running time is exponential. When we ask about the complexity, we usually implicitly mean the worst-case running time. Therefore, the complexity is exponential. Even though sometimes you might do much less work than that, sometimes you do fully exponential work, so we call the complexity exponential.

Unfortunately, I'm not aware of any simple rule of thumb that suffices for this case. Sometimes you have to figure out what's going on, and that might require a more deep analysis.

$\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.