[Question]
  [
Given a string \$ x \$, we say another string \$ y \$ is half of it, if both of the following properties are true:
* \$ y \$ is a (not necessarily continuous) subsequence of \$ x \$ - there exists a strictly increasing sequence \$ a\_i \$ such that \$ y\_i = x\_{a\_i} \$
* Each character appears in \$ x \$ exactly twice as many times as it appears in \$ y \$
For example, "acb", "bac" and "bca" are all halves of "baccba", but "abc" and "ac" aren't.
Given a string with English a-z characters (you can choose if you want it lowercase or uppercase), which you are guaranteed all characters appear an even number of times in, output an arbitrary half of it.
# Test Cases
```
"aaaabbbb" -> "aabb"
"abab" -> "ab", "ba"
"aabbaa" -> "aab", "aba", "baa"
"aabbaaaa" -> "aaba", "abaa", "baaa"
"baccba" -> "acb", "bac", "bca", "cba"
"aabbcc" -> "abc"
"abcabc" -> "abc", "acb", "bac", "bca", "cab"
```
# Rules
* You can use any reasonable I/O format.
* You can print any half of it, or a list containing any non-empty subset of its halves, with or without duplicates.
* The distribution of the output can be whatever you want, as long as only valid outputs have a non-zero chance to be selected.
* [Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) are disallowed.
This is code golf, so the shortest answer wins.
  
[Answer]
# [Python](https://www.python.org) NumPy, 36 bytes
```
lambda s:s[sorted(s.argsort()[::2])]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vweI025ilpSVpuhY3VXISc5NSEhWKrYqji_OLSlJTNIr1EovSQWwNzWgrK6NYzVioWr3M3AKgsEJeaW5BJVdBUWZeiUaaBpinVxQfHa2llJiUmJiclJyoFBurqQnRtWABhAYA)
Takes and returns arrays of characters.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 23 bytes
```
a=>a.filter(c=>a[c]^=1)
```
[Try it online!](https://tio.run/##jc@xCsMwDATQvZ@RJfZQQefg/khIQb7awcFYJQn9fUdroYOOGzQ8DrTxlw/s5XPem7xTz6FzeDLlUs@0O@g9Y3mFh@@QdkhNVGV12c1ENLAmaobF0yaluXH0frr9k5EtSteYrc4iIwPRuAhY/oD21/UL "JavaScript (Node.js) – Try It Online")
[Answer]
# [BQN](https://mlochbaum.github.io/BQN/), 6 bytes
```
⊢/˜2|⊒
```
[Try it at BQN REPL](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAg4oqiL8ucMnziipIKRsKoIOKfqCJhYWFhYmJiYiIsImFiYWIiLCJhYWJiYWEiLCJhYWJiYWFhYSIsImJhY2NiYSIsImFhYmJjYyIsImFiY2FiYyLin6k=)
BQN's "Occurrence count" (`⊒`) operator, which returns a number for each element indicating how many previous elements match it, is pretty useful here.  
Select elements from the input (`⊢/˜`) specified by the occurrence count of each of them (`⊒`) modulo 2 (`2|`).
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 3 bytes
```
p~j
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/pfXa6koGunoFRu/6htw6Ompoe7Omsfbp3wv6Au6///aKVEIEgCAiUdpcSkRDAF5CcmwhlgZlJicnISTCw5Gaw4GYiUYgE "Brachylog – Try It Online")
(`jp` with reversed I/O appears not to work.)
Originally, I had `⊇.jp?∧` (which [can generate all halves, with an extreme volume of duplicates](https://tio.run/##SypKTM6ozMlPN/pfXa6koGunoFRu/6htw6OmpofbFqQ83NVZ@3DrhP8FdVl6ao@62v//j1ZKBIIkIFDSUUpMSgRTQH5iIpwBZiYlJicnwcSSk8GKk4FIKRYA)), but it turns out that [the order in which `p` tries permutations maximizes the length of the prefix of items which are not rearranged](https://tio.run/##SypKTM6ozMlPN/r/3/TR/GUF1eVKVgqleckZiXnpqSkKBUWpaZkVCvlpCkrl9o/apiQ@amoEUnVApTYPd3UqPupYYQCkax91Lf3/HwA). So:
```
p      Permute the input such that
 ~j    the output is a string which concatenated with itself is the input.
```
It appears that the output is guaranteed to be in a valid order because of this, but I'm not entirely sure--[relevant](https://www.swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#permutation/2) [source](https://www.swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#select/3) if anyone else wants to reason through it, or engineer a counterexample.
[Answer]
# [J](http://jsoftware.com/), 11 bytes
```
#~2|1#.]=]\
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/leuMagyV9WJtY2P@a3KlJmfkK6QpqCcmJiUlJqpD@GCeuoKuFUQGxAPyYXIImaREJNFEhAZko5ISk2ESQGZyEsKOpGRkHcnJ2CSSkkG8/wA "J – Try It Online")
* `#~` Filter by
* `2|1#.]=]\` Prefixes where the count of items that equal the last item is odd.
Just noticed this is the same approach as the BQN answer, though this one I arrived at independently after waking up today.
## port of loopy walt's answer, 14 bytes
```
{~[:/:~_2{.\/:
```
[Try it online!](https://tio.run/##bYsxCsJAEEX7nGKI4BpjZtVyMBAUrMTC1oDMDAZJkwNE9urrbrFsCosZ/vuPP/oSzQAtgYEd7IHCNQiXx@3qZ/ckS@51nLG35KvifkZYhbJG66jbbGvbnzC8NX6xKg9dW7z1M4FhFjHQEAwxRwqcXDbCi5bzQIQ5CWFNIkQVzgtdLlT/CdFI/gc "J – Try It Online")
Port of [loopy walt's excellent idea](https://codegolf.stackexchange.com/a/250225/15469).
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 8 bytes
```
ṗṠ'ds?s=
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCLhuZfhuaAnZHM/cz0iLCIiLCJiYWNjYmEiXQ==)
Tack on a `;U` if halves must be unique.
```
ṗṠ       # Subsequences as strings
  '      # Filtered by
   ds    # It doubled, sorted
       = # Equals...
     ?s  # The input sorted
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 9 bytes
```
Φθ﹪№…θκι²
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gKDOvRMMtM6cktUijUEfBNz@lNCdfwzm/FCjsXJmck@qckV8AksnW1FHIBGIjTU1N6///ExWSEvOAUCGJ679uWQ4A "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
 θ          Input string
Φ           Filtered where
   №        Count of
       ι    Current character in
     θ      Input string
    …       Truncated to length
      κ     Current index
  ﹪     ²   Is odd
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 5 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Ụm2Ṣị
```
**[Try it online!](https://tio.run/##y0rNyan8///h7iW5Rg93Lnq4u/v////JyYmJiUmJSUnJQDIxMRkA "Jelly – Try It Online")** Or see the [test suite](https://tio.run/##y0rNyan8///h7iW5Rg93Lnq4uxvI3nK4/VHTmsj//xOBIAkIuBKTEoEEkJ2YCKWAjKTE5OQkCD85GagkGYgA "Jelly – Try It Online").
### How?
Same idea [loopy walt had](https://codegolf.stackexchange.com/a/250225/53748).
```
Ụm2Ṣị - Link: list, X
Ụ     - grade X up -> indices sorted by value
 m2   - mod2 slice -> 1st, 3rd, 5th, etc.
   Ṣ  - sort
    ị - index into X
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~34~~ ~~29~~ ~~26~~ ~~24~~ 23 bytes
```
Select[g@#*=-1&]
_g=1>0
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7Pzg1JzW5JDrdQVnLVtdQLZYrPt3W0M7gf0BRZl5JtLKuXZqDc0ZiUWJySWpRsYNyrFpdcHJiXl01l1IiECQBgZIOkJ2UCKGBIomJCBaEnZSYnJwEF01OhuhIBiIlrtr/AA "Wolfram Language (Mathematica) – Try It Online")
Input and output a list of characters. Keeps every other occurrence of each letter, starting from the second.
```
_g=1>0              per-character indicator
Select[        ]    keep in input where:
       g@#*=-1&       negate corresponding indicator
                      (-True is not truthy)
                    (all indicators receive an even # of negations,
                     so are reusable)
```
[Answer]
# [Perl 5](https://www.perl.org/) `-p`, 27 bytes
```
for$c(a..z){s/$c.*?\K$c//g}
```
[Try it online!](https://tio.run/##K0gtyjH9/z8tv0glWSNRT69Ks7pYXyVZT8s@xlslWV8/vfb//0QgSAICrsSkRCABZCcmciUlJicnJYJ5yclAmWQg@pdfUJKZn1f8X7cAAA "Perl 5 – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/) + `-lF -M5.10.0`, 20 bytes
```
say grep++${$_}%2,@F
```
[Try it online!](https://dom111.github.io/code-sandbox/#eyJsYW5nIjoid2VicGVybC01LjI4LjEiLCJjb2RlIjoic2F5IGdyZXArKyR7JF99JTIsQEYiLCJoZWFkZXIiOiIjIHRoaXMgaXMgbmVlZGVkIHRvIHJ1biBtdWx0aXBsZSB0ZXN0c1xuJHskX309MGZvciBhLi56OyIsImFyZ3MiOiItbEZcbi1NNS4xMC4wIiwiaW5wdXQiOiJhYWFhYmJiYlxuYWJhYlxuYWFiYmFhXG5iYWNjYmFcbmFhYmJjY1xuYWJjYWJjIn0=)
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 5 bytes
```
⇧y_sİ
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJBIiwiZiIsIuKHp3lfc8SwIiwi4oiRIiwiYWFhYWJiYmJcbmFiYWJcbmFhYmJhYVxuYWFiYmFhYWFcbmJhY2NiYVxuYWFiYmNjXG5hYmNhYmNcbmFiYWFjYmNhIl0=)
Port of loopy walt's answer. I/O as list of chars.
```
⇧y_sİ
⇧     # Grade up
 y_   # Every other item starting from the first
   s  # Sort
    İ # Index into the input
```
`y_` (uninterleave, pop) could alternatively be `2Ḟ` (every 2nd item).
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 34 bytes
```
(.)(?=(?(\1)((?<-3>)|()).|.)*$)\3
```
[Try it online!](https://tio.run/##K0otycxL/K@q4Z7wX0NPU8PeVsNeI8ZQU0PD3kbX2E6zRkNTU69GT1NLRTPGmOv//0QgSAICrsSkRCABZCcmciUlJicnJYJ5yclAmWQgAgA "Retina 0.8.2 – Try It Online") Link includes test cases. Explanation:
```
(.)(?=
```
Capture a character, then looking ahead...
```
(?(\1)
```
... if the initial character appears, then...
```
((?<-3>)|())
```
... unset `$3` if it's set, otherwise set it to the empty string...
```
.|.)*$)
```
... and check all the remaining characters in the string.
```
\3
```
If `$3` is set at this point (i.e. has been toggled an odd number of times), then...
```
```
... delete the character.
[Answer]
# [lin](https://github.com/molarmanful/lin), 40 bytes
```
.#n.n `pset"2rep.n \;.' eq"`#
.(""sort )
```
[Try it here!](https://replit.com/@molarmanful/try-lin) Outputs an iterator of subsequences.
For testing purposes (use `-i` flag if running locally):
```
"abcabc" ; `_
.#n.n `pset"2rep.n \;.' eq"`#
.(""sort )
```
## Explanation
Similar to @emanresu A's answer. Prettified code:
```
.#n .n `pset ( 2rep .n (.( ""sort )).' eq ) `#
```
* `.#n` input as *n*
* `.n `pset` powerset of *n*
* `(...) `#` filter each subsequence *s*...
	+ `2rep` repeat *s*
	+ `.n` push *n*
	+ `(.( ""sort )).'` sort *s* and *n*
	+ `eq` check if equal
[Answer]
# [Curry (PAKCS)](https://www.informatik.uni-kiel.de/%7Epakcs/), 28 bytes
```
f[]=[]
f(a:b++a:c)=a:f(b++c)
```
[Try it online!](https://tio.run/##Sy4tKqrULUjMTi7@/z8tOtY2OpYrTSPRKklbO9EqWdM20SpNA8hO1vyfm5iZp2CrkKaglJiYlJQIBEr/AQ "Curry (PAKCS) – Try It Online")
This may returns multiple results, with duplicates, but not necessarily all of them. If this is not allowed, you can add the flag `:set +first` to print only the first result: [Try it online!](https://tio.run/##DcZNCoAgEAbQfaeQVop0gQFPIi4@hyakH0Jt0eWbfKvHT63vcmPnpioxhZgmsaDsPYhdAIkdZ6cnymWCETMDOWOY9WM5sDWltnb1UmrrPw "Curry (PAKCS) – Try It Online").
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 7 bytes
```
q#.-QTy
```
[Try it online!](https://tio.run/##K6gsyfj/v1BZTzcwpPL/f6WkxOTkpEQlAA "Pyth – Try It Online")
Returns the half of the input which occurs last in the input, repeated for every time it appears as a subsequence of the input.
```
q#.-QTy
      y  subsequences of input
 #       filtered by
  .-QT   multiset difference with input
q        equals the subsequence
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 13 bytes
```
®;©ṛ
Ç®ċ%2
ÇƇ
```
[Try it online!](https://tio.run/##y0rNyan8///QOutDKx/unM11uP3QuiPdqkZAxrH2/w93bznc/qhpTeT//4lAkAQEXIlJiUACyE5MhFJARlJicnIShJ@cDFSSDEQA "Jelly – Try It Online")
```
® (load register)
 ; (concatenate with [tacit argument, character we're filtering])
  © (store result of previous link in register)
   ṛ (return right argument [tacit argument, character we're filtering])
Ç (previous link as a monad, [v=character, new_v=character])
 ®ċ (count occurrences of [character] in register)
 %2 (mod2 of [count])
Ç (previous link as monad, [v=character, new_v=1 or 0])
 Ƈ (filter all items, keeping all that satisfy condition, [v=argument])
```
Filter each character, storing them in a growing list of previous seen characters. Every time you see a character for an odd numbered time, keep it.
[Answer]
# x86-64 machine code, 12 bytes
```
AC 84 C0 0F BB C2 77 01 AA 75 F5 C3
```
[Try it online!](https://tio.run/##fVLBctsgED2zX7FVxxMUyxnHTX2wq15y7qWnzsQ5IEA2GYQ0gFq5Hv963UWKk57KAMvuvn27LMiuW@ylvFxEaJDj94zD3d62lbBYQ@03zCsvnEKtBqg3zLYqVMCiDhGFLWgBq6JM7gK1GIC9CAzAQmwJFzbsxf0mIuZ1hDzDfAt6iNo7zB4zPP1sjcKay4PweOt16G0sULaOyCdbyLc4gfz/UWeAj8ZJ2yuNX0JUpr07fAUA4yI2wjiewwnYCDeu6@PT6vP6ucCJbVS2wH4djNXIgxSu5tksZMUEzrEs8T4HRhSs88SZ3Iv71TuColndeuQpocESl1sSH0p8IDmfU@wYzOge1xu8B/7DuU6UE2J0nVPGPqbC@c3O3SQj2a4BO/dNyINxmvqh9CZL7lTBkCoo8EiqavF0heNsufpBCY4l570LZu@0Gnt4m9f50zCfP1Mn8bUNx1T@cnj8lEjfGPjMYHWk9893jpgGcp7p89CoaICoBG10FuJV0KESUlaTLiVBJE0IWgdQrWohCk8TRNcJayFq0TQiaqAXliYYeuc/srZiHy6LZv1AG/3UkqrR9i8)
Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI.
In assembly:
```
f:  lodsb           # Load a byte from the string into AL, advancing the pointer.
    test al, al     # Set flags based on that byte. In particular, ZF=1 iff it's 0.
    btc edx, eax    # Invert the bit in EDX indexed by the low 5 bits of that byte.
                    #  Set CF to the previous value of that bit. Leave ZF unchanged.
    ja s            # Jump if CF and ZF are both 0.
    stosb   # (If CF=1 or ZF=1) Add the byte to the output, advancing the pointer.
s:  jnz f           # Jump back, to repeat, if ZF is 0.
    ret             # Return.
```
Because EDX is not initialised, this can keep either the odd instances or the even instances of each letter; either possibility is acceptable. In the TIO demonstration, a `RDRAND` instruction is added to show multiple possibilities.
[Answer]
# [R](https://www.r-project.org), 24 bytes
```
\(x,`+`=order)x[!++x%%2]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=PU5BCsIwELz3FwYKuzRePHnJS6zQTUyhEmzIRmj7FS_14B_8Sn9jTNBhYWZ2FnYez7Buir0bomphRuuAY8geZikEYnUdh1vKFvTE0cIizegcebYqxVWvXvfY74_vFibZNZ0aw8UGnE67ppnq-nAu8UZM3rsZDAhK0AlCCtKUKXmiv8hSkzH6tzMmH5s0AmULjN9W0ENpyphQHq1r4Q8)
[Answer]
# [Octave](https://www.gnu.org/software/octave/) / MATLAB, ~~31~~ 30 bytes
```
@(s)s(j^2.^sum(triu(s==s'))>0)
```
Anonymous function that inputs and outputs character vectors.
The code keeps each character that has appeared an even number of times so far.
[Try it online!](https://tio.run/##ZcwxCoAwDAXQ3Ys0XYK4VzxJIY0WKohiqtePmYTSz1/y@OTkSu@mOSCiLiBeYI8TRnkOqHd5QEIQ5/08el2LXJDBkSVZjIffErW3LYh6aS0Rc@pWzO1ntproBw)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 7 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
ηε¤¢É}Ï
```
Outputs the first valid prefix.
[Try it online](https://tio.run/##yy9OTMpM/f//3PZzWw8tObTocGft4f7//5MSk5OTEgE) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfaXL/3Pbz209tOTQosOdtYf7/@v8j1ZKBIIkIFDSUUpMSgRTQH5iIpwBZiYlJicnwcSSk8GKk4FIKRYA).
Or alternatively (port of [*@emanresuA*'s Vyxal answer](https://codegolf.stackexchange.com/a/250215/52210)):
```
æʒº{I{Q
```
Outputs a list of all valid results, with duplicates.
[Try it online](https://tio.run/##yy9OTMpM/f//8LJTkw7tqvasDvz/PykxOTkpEQA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeWhlf8PLzs16dCu6kPrqgP/1@r8j1ZKBIIkIFDSUUpMSgRTQH5iIpwBZiYlJicnwcSSk8GKk4FIKRYA).
**Explanation:**
```
η        # Get all prefixes of the (implicit) input-string
 ε   }   # Map each prefix to:
  ¤      #  Push its last character (without popping)
   ¢     #  Count how many times this character occurs
    É    #  Check if the count is odd
      Ï  # Keep all characters of the (implicit) input-string at the truthy indices
         # (after which this string is output implicitly)
æ        # Get the powerset of the (implicit) input-string
 ʒ       # Filter it by:
  º      #  Mirror it (to duplicate its characters)
   {     #  Sort its characters
      Q  #  Check if it's equal to
    I{   #  The input-string with sorted characters as well
         # (after which the filtered list is output implicitly)
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~46~~ 45 bytes
*-1 Thanks to @Command Master*
```
f=lambda s:s and s[:s.count(s[0])%2]+f(s[1:])
```
[Try it online!](https://tio.run/##K6gsycjPM/7/P802JzE3KSVRodiqWCExL0WhONqqWC85vzSvRKM42iBWU9UoVjsNyDS0itX8X1CUCRRP01BKBIIkIFDS1ORCCCYlogkA1SQmYhFCE0xKTE5OwlSXnIxmfDIQAYX@AwA "Python 3 – Try It Online")
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 25 bytes
```
^
,
+`,(.)(.*)\1
$1,$2
,
```
[Try it online!](https://tio.run/##K0otycxL/K@q4Z7wP45Lh0s7QUdDT1NDT0szxpBLxVBHxQgo@P9/IhAkAQFXYlIikACyExO5khKTk5MSwbzkZKBMMhABAA "Retina 0.8.2 – Try It Online") (Test harness borrowed from [Neil's answer](https://codegolf.stackexchange.com/a/250221/16766).)
### Explanation
```
^
,
```
Insert a comma at the beginning of the string. (Any non-alphabetic delimiter will do.)
```
+`,(.)(.*)\1
$1,$2
```
Repeat until the regex no longer matches: Match the delimiter, the next character after it (group 1), any run of characters (group 2), and the character from group 1 again. Replace with the character from group 1, the delimiter, and group 2.
In effect: Comb through the string from left to right. On each iteration, move the first character to the output section, and delete another copy of that character from later in the string.
```
,
```
Remove the delimiter.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~70~~ 67 bytes
* Saved three bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat): using K&R-style argument type declaration and a neat `write.2` call to branch on printing a pointed-to character.
```
p[91];main(_,a)char**a;{for(++a;**a;++*a)write(1,*a,!(p[**a]^=1));}
```
[Try it online!](https://tio.run/##S9ZNT07@/78g2tIw1jo3MTNPI14nUTM5I7FISyvRujotv0hDWzvRGsTR1tZK1CwvyixJ1TDU0UrUUdQoiAaKx8bZGmpqWtf@///fMcrR0dHJyQUInZ1dXKIA "C (gcc) – Try It Online")
]