Sachverhalt:
A.
Das Strafgericht des Kantons Basel-Stadt verurteilte X._ am 22. Oktober 2014 wegen qualifizierten Raubes und Führens eines Motorfahrzeugs trotz Entzug des Ausweises zu einer Freiheitsstrafe von 22 Monaten als Zusatzstrafe zu Urteilen des Landgerichts Freiburg (D) wegen Widerhandlungen gegen das D-Betäubungsmittelgesetz (45 Monate) und des Tribunal correctionnel de Mulhouse (F) wegen Fahren trotz Führerscheinentzugs (2 Monate).
Die von X._ dagegen erhobene Berufung wies das Appellationsgericht des Kantons Basel-Stadt am 30. März 2015 ab.
B.
X._ führt Beschwerde in Strafsachen. Er beantragt, die Zusatzstrafe sei auf 13 Monate herabzusetzen; eventualiter sei die Sache an die Vorinstanz zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege.
Das Appellationsgericht und die Staatsanwaltschaft Basel-Stadt beantragen, die Beschwerde sei abzuweisen. A._ und B._ verzichten auf Vernehmlassungen.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung von § 35 Abs. 2 Ziff. 2 des Gesetzes betreffend Wahl und Organisation der Gerichte sowie der Arbeitsverhältnisse des Gerichtspersonals und der Staatsanwaltschaft (Gerichtsorganisationsgesetz, GOG) des Kantons Basel-Stadt. Das Strafgericht (erstinstanzliches Gericht) habe als Dreiergericht geurteilt und dürfe demnach nur Freiheitsstrafen bis zu 5 Jahren aussprechen. Ausschlaggebend für die Bestimmung der Strafgewalt sei jedoch nicht die Zusatzstrafe von 22 Monaten, sondern die dieser "zugrundeliegende" hypothetische Gesamtstrafe von 5 3⁄4 Jahren. Gemäss bundesgerichtlicher Rechtsprechung habe das Gericht, welches die Zusatzstrafe ausspricht, eine Neubewertung sämtlicher Strafen vorzunehmen. Die Zusatzstrafe von 22 Monaten sei demnach keine autonome Strafe, sondern ergebe sich rein mathematisch aus der hypothetischen Gesamtstrafe von 5 3⁄4 Jahren, von denen die Vorinstanz die Strafen des Landgerichts Freiburg (3 Jahre und 9 Monate) und des Tribunal correctionnel de Mulhouse (2 Monate) abgezogen habe. Entgegen der Ansicht der Vorinstanz verstosse eine Rückweisung der Sache zur Neubeurteilung an die Kammer des Strafgerichts im Falle funktioneller Unzuständigkeit gegen das Verschlechterungsverbot gemäss Art. 391 Abs. 2 StPO. Der Beschwerdeführer könne nicht als Folge seiner eigenen Berufung von einem Gericht mit weitergehender Strafkompetenz beurteilt werden. Die (hypothetische) Gesamtstrafe sei aufgrund der Strafkompetenz des Strafgerichts als Dreiergericht auf 5 Jahre begrenzt, woraus eine Zusatzstrafe von 13 Monaten resultiere.
1.2. Die Vorinstanz erwägt, vorweg sei festzuhalten, dass im Falle der Unzuständigkeit des Dreiergerichts entgegen der Ansicht des Beschwerdeführers eine Reduzierung der Zusatzstrafe auf 13 Monate nicht in Frage komme, sondern die Sache an das erstinstanzliche Gericht zur Beurteilung durch die Kammer des Strafgerichts als zuständiger Spruchkörper zurückzuweisen sei.
Die Vorinstanz führt zusammengefasst aus, dass die Frage der Strafkompetenz bei Ausfällung einer Zusatzstrafe - soweit ersichtlich - höchstrichterlich noch nicht entschieden worden sei und auch in der Lehre so gut wie nicht thematisiert werde. Das baselstädtische GOG bestimme die Zuständigkeit hinsichtlich der Strafkompetenzen der einzelnen Abteilungen des Strafgerichts (Kammer, Dreiergericht, Einzelgericht) nach der zu erwartenden Strafe oder Massnahme und enthalte diesbezüglich keine speziellen Ausführungen oder Vorbehalte zur Ausfällung von Zusatzstrafen. Dass gemäss bundesgerichtlicher Rechtsprechung das die Zusatzstrafe aussprechende Gericht eine Neubewertung der alten Strafen vornehmen solle, spreche dagegen, die Strafgewalt nach der tatsächlich verhängten Zusatzstrafe zu bestimmen. Allerdings dürfe das die Zusatzstrafe fällende Gericht die rechtskräftigen Strafen nicht ändern, sondern die Neubewertung könne sich nur in der Höhe der Zusatzstrafe niederschlagen. Selbst wenn die rechtskräftige (n) Strafe (n) als deutlich zu milde beurteilt werden müsste (n), könne das Gericht keine Erhöhung der Zusatzstrafe vornehmen, sondern allenfalls von einer deutlichen Milderung absehen. Die Neubewertung der rechtskräftigen Grundstrafe zwecks Bildung einer hypothetischen Gesamtstrafe verschaffe Art. 49 Abs. 2 StGB als Strafmilderungsvorschrift Geltung und solle eine Schlechterstellung des Täters (infolge getrennter Beurteilung) vermeiden. Das die Zusatzstrafe aussprechende Gericht besitze jedoch keine Vollkompetenz, weshalb die Zuständigkeiten der Abteilungen des Strafgerichts im Sinne von § 35 GOG/BS auch bei Zusatzstrafen einzig von der konkret ausgesprochenen Strafe abhängig zu machen seien.
1.3.
1.3.1. Gemäss § 35 GOG/BS richtet sich die Zuständigkeit der einzelnen Abteilungen der Strafgerichte nach der zu erwartenden Strafe oder Massnahme. Gemäss Abs. 2 Ziff. 2 der Norm kann das Dreiergericht Busse, Geldstrafen, gemeinnützige Arbeit oder Freiheitsstrafen bis zu fünf Jahren (Art. 34 - 55 StGB), therapeutische Massnahmen (Art. 56 - 63b StGB) und andere Massnahmen (Art. 66 - 73 StGB) verhängen.
1.3.2. Die Auslegung und Anwendung kantonalen Rechts prüft das Bundesgericht nur unter dem beschränkten Gesichtswinkel der Willkür (Art. 95 BGG; <ref-ruling> E. 2.3 S. 387; <ref-ruling> E. 2 S. 15). Das Vorbringen ist einlässlich zu begründen; es gilt das strenge Rügeprinzip (vgl. Art. 106 Abs. 2 BGG; Urteil 6B_478/2015 vom 12. Februar 2016 E. 2.2.1 mit Hinweisen). Willkürlich ist ein Entscheid nach konstanter Praxis nicht schon dann, wenn eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, sondern nur, wenn er offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Erforderlich ist, dass der Entscheid nicht nur in der Begründung, sondern auch im Ergebnis willkürlich ist (<ref-ruling> E. 2.1 mit Hinweisen).
1.4. Die Beschwerde erweist sich im Ergebnis als unbegründet. Zwar hätten die kantonalen Gerichte für die in der Schweiz begangenen Taten des qualifizierten Raubs und des Führens eines Motorfahrzeuges trotz Ausweisentzugs keine Zusatzstrafe aussprechen dürfen, sondern diese eigenständig beurteilen müssen. Dies führt vorliegend aber nicht zur Aufhebung des angefochtenen Entscheides, da das Ausfällen einer Zusatzstrafe eine erhebliche Strafminderung und damit Privilegierung des Beschwerdeführers nach sich zieht und auf die ausgesprochene Strafe aufgrund des Verschlechterungsverbots nicht zu dessen Ungunsten zurückgekommen werden kann (vgl. Art. 391 Abs. 2 StPO).
1.4.1. Die Voraussetzungen für die Ausfällung einer Zusatzstrafe gemäss Art. 49 Abs. 2 StGB sind vorliegend nicht erfüllt. An der bisherigen Rechtsprechung, der die herrschende Lehre ohne Auseinandersetzung in der Sache folgt, wonach eine Zusatzstrafe auch zu einem ausländischen Urteil ausgefällt werden kann, welches Taten betrifft, die nicht in den (räumlichen) Geltungsbereich des StGB fallen (<ref-ruling> E. 8.2 S. 105; <ref-ruling> E. II/5a/cc; statt vieler: CHRISTOF RIEDO, Retrospektive Intransparenz, Bemerkungen zu Art. 49 Abs. 2 StGB, in: Droit pénal et diversités culturelles, Mélanges en l'honneur de José Hurtado Pozo, 2012, S. 344 mit zahlreichen Hinweisen), ist nicht festzuhalten. Eine Zusatzstrafe kann nur zu inländischen Urteilen ausgesprochen werden.
Art. 49 StGB ist eine Strafzumessungsnorm, die - wie die übrigen Normen des StGB - nur zur Anwendung gelangt, wenn die zu beurteilende Straftat der schweizerischen Gerichtsbarkeit nach den Bestimmungen über den räumlichen Geltungsbereich unterliegt. Art. 49 Abs. 2 StGB soll gewährleisten, dass das in Abs. 1 verankerte Asperationsprinzip auch bei retrospektiver Konkurrenz zur Anwendung gelangt (vgl. <ref-ruling> E. 6.1.2 S. 67; <ref-ruling> E. 3.4.1 S. 115), erweitert hingegen den Anwendungsbereich des StGB nicht. Implizite Voraussetzung für eine Zusatzstrafe gemäss Art. 49 Abs. 2 StGB ist, dass für die bereits beurteilten und noch zu beurteilenden Delikte im Falle gleichzeitiger gerichtlicher Beurteilung eine Gesamtstrafe hätte ausgesprochen werden können (vgl. <ref-ruling> E. 2.3.2). Kommt jedoch eine gemeinsame gerichtliche Beurteilung und somit eine Gesamtstrafe nicht in Betracht, da die im Ausland begangenen Straftaten nicht in den (räumlichen) Geltungsbereich des StGB fallen, muss dies auch im Rahmen retrospektiver Konkurrenz gelten. Von einer vom Gesetzgeber nicht gewollten zufälligen Ungleichbehandlung schweizerischer und ausländischer Täter kann aufgrund der umfassenden gesetzlichen Regelung der schweizerischen Strafhoheit (vgl. u.a. Art. 3 - 7, Art. 185 Ziff. 5, Art. 260ter Ziff. 3, Art. 264m StGB; Art. 19 Abs. 4 BetmG; Art. 116 Abs. 1 lit. a AuG) entgegen BGE <ref-ruling> (E. II/5a/cc) keine Rede sein. Zudem kann auf die bereits in <ref-ruling> (E. 2e) angedeuteten Schwierigkeiten verwiesen werden, die sich bei einer Anwendung von Art. 49 Abs. 2 StGB auf Auslandsurteile ergeben können.
Neben dem Vorliegen der schweizerischen Gerichtsbarkeit setzt die Ausfällung einer Zusatzstrafe gemäss Art. 49 Abs. 2 StGB voraus, dass die frühere Tat durch eine inländische Strafbehörde (materiell) beurteilt wurde. Denn auch in Fällen sog. doppelter Strafbarkeit der früheren Tat (vgl. hierzu: JÜRG-BEAT ACKERMANN, in: Basler Kommentar, Strafrecht I, 3. Aufl. 2013, N. 161 zu Art. 49 StGB; H ANS SCHULTZ, Einführung in den allgemeinen Teil des Strafrechts, Zweiter Band, 4. Aufl. 1982, S. 82; DERS., ZBJV 1991 S. 52) übernimmt das Schweizer Gericht (respektive die Schweizer Strafbehörde) die im Ausland ausgesprochene Strafe nicht, sondern rechnet diese - soweit vollzogen - auf die von ihm auszusprechende Strafe an (vgl. Art. 3 Abs. 2, Art. 4 Abs. 2, Art. 5 Abs. 3, Art. 6 Abs. 4, Art. 7 Abs. 5 StGB). Dies setzt die eigene Beurteilung der früheren Tat durch eine inländische Behörde im Schuld- und Strafpunkt unter Einhaltung der prozessualen und materiellen Vorschriften voraus.
Diese Voraussetzungen sind vorliegend nicht erfüllt. Die kantonalen Gerichte hätten für die in der Schweiz begangenen Straftaten die von ihnen hierfür als angemessen erachtete Gesamtfreiheitsstrafe als eigenständige Strafe aussprechen müssen.
1.4.2. Durch das Ausfällen einer Zusatzstrafe von 22 Monaten hat das Strafgericht die ihm als Dreiergericht gesetzlich zustehende Strafgewalt von 5 Jahren nicht überschritten. Es liegt weder eine funktionale Unzuständigkeit (§ 35 Abs. 1 GOG/BS) noch eine Überschreitung der Strafkompetenz nach § 35 Abs. 2 Ziff. 2 GOG/BS vor. Das Bundesgericht hat in einem neuen, zur Publikation vorgesehenen Leitentscheid seine Rechtsprechung zur Zusatzstrafe gemäss Art. 49 Abs. 2 StGB präzisiert. Gesamt- und Zusatzstrafe bilden zwar infolge retrospektiver Konkurrenz eine gedankliche Einheit, sind aber selbstständige Strafen. Die Zusatzstrafe ist die infolge Asperation mit der Grundstrafe reduzierte Strafe für die neu zu beurteilenden Taten. Sie tritt zur Grundstrafe des rechtskräftigen Ersturteils hinzu und ergänzt diese. Die Strafgewalt des die Zusatzstrafe aussprechenden Gerichts ist auf die noch nicht beurteilte (n) Tat (en) beschränkt. Es darf im Rahmen retrospektiver Konkurrenz das rechtskräftige Urteil nicht aufheben und keine Gesamtstrafe für alle Straftaten aussprechen (<ref-ruling> E. 2.4.1 f.; vgl. auch: Jürg-Beat Ackermann, a.a.O., N. 129 f. zu Art. 49 StGB; je mit Hinweisen).
Die von den kantonalen Gerichten für die in der Schweiz begangenen Straftaten ausgesprochene Zusatzstrafe von 22 Monaten tritt als selbstständige Strafe zu den rechtskräftigen (ausländischen) Grundstrafen und liegt innerhalb der Strafkompetenz gemäss § 35 Abs. 2 Ziff. 2 GOG/BS.
1.4.3. Der Antrag des Beschwerdeführers, er sei zu einer Zusatzstrafe von 13 Monaten zu verurteilen, erweist sich bereits mangels Überschreitung der Strafkompetenz durch das erstinstanzliche Gericht als unbegründet. Eine allfällige funktionale Unzuständigkeit der Dreierkammer hätte entgegen seiner Ansicht nicht zu einer Reduzierung der Strafe, sondern zu neuer Entscheidung durch die in der Sache zuständige Kammer des Strafgerichts geführt.
2.
Die Vorinstanz wurde vom Bundesgericht bereits mehrfach darauf hingewiesen, dass sie als Berufungsgericht über umfassende Kognition in tatsächlicher und rechtlicher Hinsicht verfügt. Sie fällt ein neues, den erstinstanzlichen Entscheid ersetzendes Urteil und darf sich nicht damit begnügen, die erstinstanzliche Rechtsanwendung zu überprüfen (vgl. <ref-ruling> E. 1.3.3 S. 248; Urteil 6B_1167/2015 vom 25. August 2016 E. 1.3). Hinsichtlich der formellen Anforderungen an das Dispositiv des in der Sache ergehenden Berufungsurteils wird nochmals auf Art. 81 i.V.m. 408 StPO verwiesen (hierzu: Urteile 6B_519/2015 vom 25. Januar 2016 E. 2; 6B_811/2015 vom 13. Januar 2016 E. 3; je mit Hinweisen).
3.
Die Beschwerde erweist sich als unbegründet. Das Gesuch um unentgeltliche Rechtspflege ist infolge Aussichtslosigkeit der Rechtsbegehren abzuweisen (Art. 64 Abs. 1 BGG). Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG). Seiner finanziellen Situation ist bei der Festsetzung der Gerichtskosten angemessen Rechnung zu tragen (Art. 65 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 28. September 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Held