0 votes
What is the worst case time complexity of following implementation of subset sum problem.

// Returns true if there is a subset of set[] with sun equal to given sum

bool isSubsetSum(int set[], int n, int sum)

{

// Base Cases

if (sum == 0)

return true;

if (n == 0 && sum != 0)

return false;

// If last element is greater than sum, then ignore it

if (set[n-1] > sum)

return isSubsetSum(set, n-1, sum);

/* else, check if sum can be obtained by any of the following

(a) including the last element

(b) excluding the last element   */

return isSubsetSum(set, n-1, sum) ||

isSubsetSum(set, n-1, sum-set[n-1]);

}

## 1 Answer

0 votes
recurrence for given implementation of subset sum problem T(n) = 2T(n-1) + C1 T(0) = C1 Where C1 and C2 are some machine specific constants. The solution of recurrence is O(2^n)
answered by

0 votes
2 answers
0 votes
1 answer
0 votes
1 answer
0 votes
2 answers
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
0 answers
0 votes
1 answer
0 votes
1 answer