Exponential Time complexity(O(2^n))

help
1

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!

2

u can try travelling salesman problem

1 Like
3

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 : C - H and V

3 Likes
4

someone asked me this recently.

search for brute force tags .

1 Like
5

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.

6

They meant the problem C from that contest, not D

1 Like
7

Sorry for wrong link it’s updated now

1 Like
8

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

9

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

10

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

11

Okay Buddy Thanks!

12

this is also a good problem from a recent leetcode biweekly

1 Like
13

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:

14

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

2 Likes
15

Thank you @aneee004
I will surely check it!

1 Like
16

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
17

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