Soruyu tam olarak anlamamış olabilirim
Önce Sarı, Mavi, Yeşil'e basıyorsunuz. Yani beden seçimi yapmıyorsunuz.
Sonra bir daha renk seçimi yapmadan S, M, L'ye basıyorsunuz.
Bu durumda son seçtiğiniz renk (Yeşil) için S, M ve L seçilmiştir diyebiliriz.
Ama Sarı ve Mavi için beden seçimi yapmadığınız için onlarda hangi bedenler seçilmiş bilemeyiz.
Anladığım kadarıyla siz sırası önemli olmaksızın seçilen renk ve beden'lerin her türlü kombinasyonunu elde etmek istiyorsunuz.
Yani sadece Sarı seçilirse, sonra da S ve M seçilirse şu kombinasyon oluşsun:

Sarı/S
Sarı/M

Bundan hemen sonra Mavi seçilirse, seçilmiş her beden bu renk için de geçerli olacak:

Sarı/S
Sarı/M
Mavi/S
Mavi/M

Şimdi de mesela L seçilirse seçilmiş her renk için bu beden de geçerli olacak:

Sarı/S
Sarı/M
Sarı/L
Mavi/S
Mavi/M
Mavi/L

Ben soruyu böyle anladım. Cevabım buna göre olacak.
Örnek olarak üstteki veriyi şu şekilde tutacağım:

$_SESSION["combo"] = [
    ["Sarı", "S"],
    ["Sarı", "M"],
    ["Sarı", "L"],
    ["Mavi", "S"],
    ["Mavi", "M"],
    ["Mavi", "L"],
];

Cevapla alakasız öneri (Okumasanız da olur)
Eğer çok yoğun anlık kullanıcıya sahip bir sistem varsa session kullanımını önermiyorum. Çünkü session sunucunın hafızasında yer tutuyor. (Saklandığı yere göre ram'de veya rom'da olabilir)
Bunun yerine çok anlık kullanıcısı olan sistemlerde token'lar kullanılıyor genellikle. Token'lar şifrelenmiş halde istemci tarafında tutulan, şifresinin sadece sunucudaki anahtarla çözülebildiği string değerlerdir. İstemciye token ile şifrelenmiş halde bazı veriler iletilir ve sunucuya yapılan isteklerde mutlaka token'ın da gönderilmesi istenir. Token yoksa işlem yapılmaz. Token sunucudaki şifreyle çözülür ve değerler kontrol edilerek değiştirilip değişitirilmediği kontrol edilir. Değiştirilmişse yine işlem yapılmaz. Token, her isteğe verilen yanıtta değiştirilerek tekrar istemciye gönderilir. İstemci, her yanıtta gelen token'ı eski token'ın yerine kaydeder ve sonraki istekte göndermek için hazırda tutar. Bu yüzden hem front-end tarafında hem de back-end tarafında token yönetimi için oluşturulmuş fonksiyonlar hazırlanmalıdır.
Session kullanımındaki bir diğer sorun da CSRF açığıdır. Örneğin kullanıcınız yönetim panelinde oturum açtı ve bu kullanıcı için bir session oluşturdunuz. Artık bu kullanıcı tarayıcısını kapatana kadar bu session'la işlemler yapma yetkisine sahip oldu. Sonra kullanıcınıza bir e-posta geldi. E-posta'da da "bana tıkla" diye bir link var. Halen aynı tarayıcıyı kullanan kullanıcı bu linke tıkladı. Meğerse link, sizin sitenizdeki yönetim panelinde kullanıcının bazı verilerinin silinebildiği bir sayfaya GET metoduyla giden bir linkmiş. Sonuçta bu sayfaya atılan istek yine aynı tarayıcıdan geldiği için ve sunucu da bu tarayıcıya özel bir session'la hareket ettiği için gelen isteği karşılar ve silme işlemini yapar. Oysa ki sunucu bir token'ın varlığını kontrol ediyor olsaydı e-posta'yı gönderen kişi bu token'ı önceden bilemeyeceği için bu link'i oluşturamazdı. Zaten token'lar get parametresi olarak değil header üzerinden gönderildiği için bu tip link'lere karşı ayrıca bir güvenlik katmanı daha oluştururlar.
Sunucuda session'ın saklandığı hafıza ile ilgili bir sorununuz yoksa, yani sadece CSRF açığını kapatmak istiyorsanız, session ve token'ı birlikte de kullanabilirsiniz tabii ki.

Asıl Cevap
Siz renk veya bedene her tıklandığında sunucuya bir istek atıyorsunuz anladığım kadarıyla. Verileri de session ile tutuyorsunuz. İstiyorsunuz ki her seçiçen renk/beden değeri session içindeki bir PHP objesinde organize şekilde yerleşsin.

// POST metoduyla PHP'ye ilettiğiniz verileri değişkenlere alalım.
$selectedColor = isset($_POST["color"]) ? $_POST["color"] : false;
$selectedSize = isset($_POST["size"]) ? $_POST["size"] : false;

// Ya renk ya da beden seçilmiştir. İkisi birden aynı anda gelemez diye varsayıyorum.
// Eğer ikisi de gelmemişse bir hata mesajı gönderelim.
if(!$selectedColor && !$selectedSize) {
    echo "Renk veya beden seçimi iletilmedi!";
    exit();
}

// Daha önceden seçilmiş elemanları tuttuğumuz objeyi de bir değişkene alalım.
$currentSelections = isset($_SESSION["combo"]) ? $_SESSION["combo"] : [];

// Daha önce seçilmiş tüm renkleri ve bedenleri bulalım ve iki ayrı dizide tutalım.
$allCurrentColors = [];
$allCurrentSizes = [];
foreach($currentSelections as $selection) {
    if(!in_array($selection[0], $allCurrentColors)) $allCurrentColors[] = $selection[0];
    if(!in_array($selection[1], $allCurrentSizes)) $allCurrentSizes[] = $selection[1];
}

// Eğer yeni seçilen değer bir renk ise, 
if($selectedColor) {
    // Ve bu renk zaten daha önce eklenmişse seçilmiş renklerden kaldırılsın. (Bu renk seçimini iptal etmiş oluyoruz)
    if(in_array($selectedColor, $allCurrentColors)) {
        $allCurrentColors = array_values(array_diff($allCurrentColors,[$selectedColor]));
    }
    // Yok eğer bu renk daha önce eklenmemişse seçilmiş renklere ekleyelim.
    else {
        $allCurrentColors[] = $selectedColor;
    }
}

// Eğer yeni seçilen değer bir beden ise, yukarıda renk için uyguladığım kontrolün aynısını beden için yapalım.
if($selectedSize) {
    if(in_array($selectedSize, $allCurrentSizes)) {
        $allCurrentSizes = array_values(array_diff($allCurrentSizes,[$selectedSize]));
    }
    else {
        $allCurrentSizes[] = $selectedSize;
    }
}

// Daha önce renk veya beden için null değeri atamış olabiliriz. (Aşağıda yapıyoruz)
// Şu an için bu iki dizide de null değeri bulunmasın.
$allCurrentColors = array_values(array_diff($allCurrentColors,[null]));
$allCurrentSizes = array_values(array_diff($allCurrentSizes,[null]));

// Böylece elimizde iki ayrı dizide seçilmiş tüm renkler ve tüm bedenler mevcut. 
// Bunları birleştireceğiz ve yeni $currentSelections değeri ($_SESSION["combo"] değeri) bu birleşim olacak.
// Öncelikle mevcut seçimleri yok edelim.
$currentSelections = [];

// Şu an sadece renk seçilmiş ama hiç beden seçilmemiş olabilir.
// Veya hiç renk seçilmemiştir ama beden seçilmiştir.
// Ama hiç değeri olmayan türü (renk/beden) yeni oluşturacağımız dizide yok sayamayız.
// O yüzden değeri olmayan tür varsa bir tane null değeri atayalım.
if(count($allCurrentColors)===0) $allCurrentColors = [null];
if(count($allCurrentSizes)===0) $allCurrentSizes = [null];

// Eğer iki dizide birden sadece null değerleri kalmışsa iki diziyi de boşaltalım.
if(count($allCurrentColors)===1 && count($allCurrentSizes)===1) {
    if($allCurrentColors[0]===null && $allCurrentSizes[0]===null) {
        $allCurrentColors = [];
        $allCurrentSizes = [];
    }
}

// Her bir renk için her bir beden eklenecek.
// Tüm renkleri dönelim. Her bir renk için...
foreach($allCurrentColors as $currentColor) {
    // Tüm bedenleri dönelim. Her bir beden için...
    foreach($allCurrentSizes as $currentSize) {
        $currentSelections[] = [$currentColor, $currentSize];
    }
}

// Tüm seçimler yeniden organize olduğuna göre bu yeni değeri session'a yazabiliriz.
$_SESSION["combo"] = $currentSelections;

Kodları hiç kontrol etmedim, tek seferde çalışmayabilir. Hata ayıklamak gerekebilir...

Yazdığım kodun şu şekilde çalışmasını umuyorum:

Sayfaya ilk girildiğinde herhangi bir renk veya beden seçili değil. Bu durumda PHP'de tutulan değer şu:

$_SESSION["combo"] = [];

Sonra M bedeni seçiliyor. İlk seçim. Bu durumda PHP'de tutulan değer:

$_SESSION["combo"] = [
    [null, "M"]
];

Sonra L bedeni seçiliyor. 2. seçim de bu. Bu durumda PHP'de tutulan değer:

$_SESSION["combo"] = [
    [null, "M"],
    [null, "L"]
];

Sonra da Sarı renk seçilmiş olsun. Bu durumda:

$_SESSION["combo"] = [
    ["Sarı", "M"],
    ["Sarı", "L"]
];

Sonra da Mavi renk seçilmiş olsun. Bu durumda:

$_SESSION["combo"] = [
    ["Sarı", "M"],
    ["Sarı", "L"],
    ["Mavi", "M"],
    ["Mavi", "L"]
];

Sonra da tekrar S beden seçilsin.

$_SESSION["combo"] = [
    ["Sarı", "M"],
    ["Sarı", "L"],
    ["Sarı", "S"],
    ["Mavi", "M"],
    ["Mavi", "L"],
    ["Mavi", "S"]
];

Sonra da Yeşil renk seçilmiş olsun.

$_SESSION["combo"] = [
    ["Sarı", "M"],
    ["Sarı", "L"],
    ["Sarı", "S"],
    ["Mavi", "M"],
    ["Mavi", "L"],
    ["Mavi", "S"],
    ["Yeşil", "M"],
    ["Yeşil", "L"],
    ["Yeşil", "S"]
];

Seçimlerinden hoşnut olmamış olacak ki Mavi renk için tekrar tıklamış olsun. Bu durumda:

$_SESSION["combo"] = [
    ["Sarı", "M"],
    ["Sarı", "L"],
    ["Sarı", "S"],
    ["Yeşil", "M"],
    ["Yeşil", "L"],
    ["Yeşil", "S"]
];

Şimdi de L bedenine tekrar basmış olsun. Seçimleri arasında L olmasını istemiyormuş meğerse:

$_SESSION["combo"] = [
    ["Sarı", "M"],
    ["Sarı", "S"],
    ["Yeşil", "M"],
    ["Yeşil", "S"]
];

Şimdi bütün renk seçimlerini kaldırmak için önce Sarı sonra Yeşil renk butonlarına basmış olsun. Bu 2 istekten sonra:

$_SESSION["combo"] = [
    [null, "M"],
    [null, "S"],
];

Şimdi beden seçimlerini de kaldırmak için M ve S butonlarına da bastı diyelim. Sonuçta başa dönmüş olacak:

$_SESSION["combo"] = [];

@goko Birileri daha yanmış anlaşılan...