3082. Find the Sum of the Power of All Subsequences | 0-1 knapsack DP | Binary Exponentiation

[@nikhilbabar2226]

Great solution, got to know how different intutions get to same solution I thought in this way which might seem easier to understand: Consider a single element from array. There are 3 possibilities for it: 1) The element is present in your current array (considered subsequence) and you take it. 2) The element is present in your current array (considered subsequence) and you dont take it. 2) The element is not present in your current array (considered subsequence) If you see 2 and 3, they are same. So dontpick contributes twice. Hence, dp[i][k] = pick + 2*dontpick

[@joshthwu]

Great explanation! I spent about an hour and a half after the contest but still couldn't understand why we had to multiply by 2 when we chose not to take the number. However, I suddenly understood it during your explanation. Thanks a lot!

[@xyz956]

bro just , you related with the knapsack problem, and built on that, that was super awesome bro , thanks.

[@for_the_creators289]

my god i just did this que and burh posted it u r very great >>>>>>> fr the best no words , good luckkkkkkk

[@PrinceTiwari-md7of]

very nice explanation😃

[@avijitdey992]

thanks a lot brother

[@nishantkumarjha4644]

thanks bro..really helped

[@IK-xk7ex]

Subsequence keeps the order, subset - no order required

[@shashankvashishtha4454]

subsequence and subset are same, but the difference is that subset contain unique elements.

[@adityajhunjhunwala9739]

in subsequence order of elements matter whereas in subsets order of elements doesnt matter

[@asthajain2511]

😇

[@akb3689]

🔝

[@shashankvashishtha4454]

2^n

[@venkateshaprabhup007]

Thanks for the great explanation bro 🫂