CODEWITHSUNDEEP
algorithmsetsubset
ashwani
ashwani

Reputation: 702

Is there any algorithm to generate all subsets of a given set in O(n^2) time?

I am just trying out different algorithms for practice and I came across this problem for which I have to generate all the subsets of a given set of elements (non-duplicate).

the naive solution for this is using bitmasking technique. But that has an exponential time complexity i.e O(2^n). In the worst case scenario, value of n can be upto 100000 so in this scenario O(n^2) solution is not very eddicient.

I am just wondering if there is any other more efficient algorithm which can solve this in ~O(n^2)?

Upvotes: 0

Views: 1559

Answers (2)

John Coleman
John Coleman

Reputation: 51998

While there is clearly no polynomial time way to generate all subsets of an n element set, some ways of doing so are more efficient than others. In particular, if you use a Gray code you can go from 1 subset to another by adding or removing a single element from successive subsets. This would make e.g. brute-force knapsack solutions noticeably more efficient (for e.g. n around 30 or smaller).

Upvotes: 3

pkacprzak
pkacprzak

Reputation: 5629

If you want to for example print all the subsets or store them explicitly anywhere there is no such algorithm. Notice that there are 2^n subsets of a set of n elements and simply enumerating them requires an exponential time.

Upvotes: 3

Related Questions