Repository navigation
ADD BITWISE DP / SOS DP #7503
Description
What would you like to Propose?
Add implementation(s) of dynamic programming on bitmasks, where DP state includes a bitmask representing a subset of elements already used/visited (e.g. dp[mask][i]). Useful for problems like TSP, optimal assignment, and subset-based counting where n is small (≤ ~20) and the order/combination of included elements matters. Covers core bit tricks (set/check/clear bit, iterate submasks) along with example problems.
Issue details
Bitmask DP represents a subset of elements as bits in an integer, where bit i being 1 means element i is included. The DP state dp[mask] (or dp[mask][i]) stores the best result for that subset, and transitions move from one mask to another by adding an element via mask | (1 << i). It's used when problems involve small sets (n ≤ ~20) and require tracking exactly which elements have been chosen, e.g., TSP, optimal assignment, and subset partitioning.
Additional Information
No response
Activity
YashKumar-404 commentedon Jul 1, 2026
Hello, I would like to work on this issue. I can add a clean, well-documented Java implementation of the Traveling Salesperson Problem (TSP) using Bitmask DP, along with the necessary JUnit tests.
YashKumar-404 commentedon Jul 1, 2026
I have put together a Java implementation for the Traveling Salesperson Problem (TSP) using Bitmask DP, along with the necessary documentation.
narendrakumar9867 commentedon Jul 8, 2026
Hi @priyanka-hotkar,
Can you please look once I was trying to complete this issue and if you any doubt, please let me know!
#7517
narendrakumar9867 commentedon Jul 13, 2026
Hi, @priyanka-hotkar can you please check once this pr #7517.
if any issue still face i try to fix it.
priyankahotkar commentedon Jul 13, 2026
Hi,
I am not the maintainer of the repository, can you please tag one of them ?
github-actions commentedon Aug 13, 2026
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!
github-actions commentedon Aug 20, 2026
Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!