The dpkg database (in /var/lib/dpkg/status) stores the intended state of the package in the same line as current state as described in dpkg(1). So an installed package would have an entry similarly to this example:
# dpkg -s hello| egrep '^(Package|Status|Architecture):'
Package: hello
Status: install ok installed
Architecture: amd64
Once you use a tool to set the intention to remove it it would appear as:
# dpkg -s hello| egrep '^(Package|Status|Architecture):'
Package: hello
Status: deinstall ok installed
Architecture: amd64
With purge instead of deinstall for a to-be-purged package.
You probably selected (for deinstallation) an important package which triggered the change on others selected or a whole group of packages.
There are a few tools that can do this, among them the venerable dselect, aptitude, the lower level dpkg --set-selections or apt-mark. The latter one is easier to use but still can't be used to check what was changed (because it won't compare deinstall to installed above) and can only do one operation at a time so would be very slow on multiple fixes. dpkg --set-selections will be preffered because it can do this in one invocation.
Note that everything got a bit more complicated with multi-arch where the Architecture value has to be retrieved to distinguish a package installed twice in two architectures. Note that architecture all also works for packages without real architecture.
Here's a cancel-changes.awk script that will set the intention to be compatible with the current state: install what is installed, purge what is not and keep deinstalled what is removed (still keeping configuration files), in a format suitable for dpkg --set-selections.
#!/usr/bin/awk -f
/^Package:/ { package=$2; newintent="none" }
/^Status: (purge|deinstall) ok installed$/ { newintent="install" }
/^Status: install ok config-files$/ { newintent="deinstall" }
/^Status: install ok not-installed$/ { newintent="purge" }
/^Architecture:/ { package=package ":" $2 }
/^$/ && newintent != "none" { print package, newintent }
You should verify the output of this script before actually feeding it to dpkg --set-selections. A future release of Debian (and Ubuntu) might change the internal format.
Here's an usage example on Debian 10, to test on the victim package hello.
# apt-get install hello
[...]
# apt-mark remove hello
Selected hello for removal.
# dpkg -l hello
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Architecture Description
+++-==============-============-============-==================================
ri hello 2.10-2 amd64 example package based on GNU hello
# cancel-changes.awk < /var/lib/dpkg/status
hello:amd64 install
# cancel-changes.awk < /var/lib/dpkg/status | dpkg --set-selections
# dpkg -l hello
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Architecture Description
+++-==============-============-============-==================================
ii hello 2.10-2 amd64 example package based on GNU hello
