Subset sum problem

Question

Brute force algorithm time complexity for subset sum problem

a) O(N logN) b)O(N^2) c) O(N^2 logN) d) O(2^N)

Comments

given answer is d)

I think it should be O(N.2^N)

Answer 1

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.

and the amount of work done is O(2^N)

so from that work done , i guess the brute force complexity will be D

Comments

I don't think we can apply divide and conquer paradigm if they have said brute force

Here they have said Brute Force so our approach should be like this

1. Generate all subsets  which will be  2^N subsets

2. compute the sum for each subset and check if it is the required sum. This will take O(N)

So,total time complexity  O(N.2^N)

---

it is not O(N*2^N) it should be O(2^N)+O(n)= O(2^N)-------which results into this

---

O(N) time will be taken for summation of each subset so it will be O(N.2^N) for all subsets