Efficient way to check if sum is possible from a given set of numbers

Asked Jul 28 '17 at 15:02

Active Jul 28 '17 at 15:02

Viewed 88 times

Given a set of unique positive integers (size ranging upto 32), it is required to determine whether a required sum is possible or not.

A brute force approach is:

bool isPossible(long long int n, int s)
{
    if(n<0)
        return false;
    if(n == 0)
        return true;
    for(int i=s;i<32;++i)
        if(isPossible(n-allNumbers[i], i+1))
            return true;
    return false;
}

isPossible(n,0) returns the boolean value corresponding to whether the number n is possible to be expressed as sum of unique numbers from the set allNumbers[]. But the complexity of this solution is O(2^32). Is it possible to get a better run time for this problem?

asked Jul 28 '17 at 15:02

yobro97

1,125
8
23

1

O(2^32) would be constant time. pretty sure you got you notation wrong here. – litelite Jul 28 '17 at 15:06
@NathanOliver Thank you! – yobro97 Jul 28 '17 at 15:07
@litelite it is `2^N` if the size of set is `N` – yobro97 Jul 28 '17 at 15:09
@litelite if the number of positive integers is always `32` then the complexity is indeed constant – 463035818_is_not_an_ai Jul 28 '17 at 15:09
So your complexity should be O(2^N) because in the algorithm the size of `allNumber` might change. – litelite Jul 28 '17 at 15:11

Efficient way to check if sum is possible from a given set of numbers

0 Answers0