Exponential Time complexity(O(2^n))

Where can i find such problems whose solutions have an exponential time complexity like O(2^n)
I know problems having constraints like n<25 will be solved with solution having exponential time complexity like O(2^n).

But how can i find those problems.Is there any special tag for them?I am not able to find them.
If Anyone can help , Thanks in Advance!

u can try travelling salesman problem

1 Like

sort by brute force tag in codeforces you’ll find few of them ,you might also try this problem from a recent atcoder ABC :
PROBLEM_LINK : https://atcoder.jp/contests/abc173/tasks/abc173_c

3 Likes

someone asked me this recently.
https://codeforces.com/contest/476/problem/B?mobile=false

search for brute force tags .

1 Like

Thanks For the Reply,

I searched for Bruteforce Tags but all maximum problems have constraints like 1000 or 100 but i wanted n<25.
Brother the link you sent have constraints 10^5, I am sure solution will not be having 2^n complexity right?
Can you send any other link.

They meant the problem C from that contest, not D

1 Like

Sorry for wrong link it’s updated now

1 Like

You are right
Thank you so much!
Correct link - Click Here

No Problem Brother It Happens!
Btw Thanks for the help!

Thank You So much,This is type of problem which i am looking for!

Okay Buddy Thanks!


this is also a good problem from a recent leetcode biweekly
1 Like

Thanks Brother, Actually i came across a problem which i know that it will be solved by considering all possibilities but i am not able to think how to implement that so i thought i should practice some problems having 2^n solution.

Have you came across a problem which includes matrix and we have to consider all possibilities(2^n),(btw that Atcoder problem is also a matrix one but if there are similar problems) if yes please send link to that problem.
If no, I will search it to practice :slightly_smiling_face:

You can try this too.
(It’s a hard question though).

2 Likes

Thank you @aneee004
I will surely check it!

1 Like

The editorial for this problem uses bitmak dp which is O(2^n), however, I solved it in polynomial time.

Bitmask Dp is an interesting topic. The runtime of a bitmask dp algorithm is generally O(2^n). The gfg link might be confusing at first, I’d suggest you see this or/and read this if you want to learn bitmask dp.

4 Likes

Buddy,you’re such a help!
Thanks!
I am first solving that Atcoder problem mentioned above then i will switch to this problem!

1 Like