Did the Israelites walk bare foot in the desert, or did they have shoes (comment on Deut. 8:4)?

Question

Deuteronomy 8:4 says

שִׂמְלָ֨תְךָ֜ לֹ֤א בָֽלְתָה֙ מֵֽעָלֶ֔יךָ וְרַגְלְךָ֖ לֹ֣א בָצֵ֑קָה זֶ֖ה אַרְבָּעִ֥ים שָׁנָֽה׃

Your clothes did not get old upon you, neither did your feet swell, these forty years.

Rashi on Deuteronomy 8:4:2:

לא בצקה. לא נפחה כבצק, כדרך הולכי יחף שרגליהם נפוחות:

It did not swell as dough. Like those who walk bare foot, whose feet swell.

Rash"i seems to imply that they walked bare foot. Yet, in Deuteronomy 29:4, it says:

וָאוֹלֵ֥ךְ אֶתְכֶ֛ם אַרְבָּעִ֥ים שָׁנָ֖ה בַּמִּדְבָּ֑ר לֹֽא־בָל֤וּ שַׂלְמֹֽתֵיכֶם֙ מֵעֲלֵיכֶ֔ם וְנַֽעַלְךָ֥ לֹֽא־בָלְתָ֖ה מֵעַ֥ל רַגְלֶֽךָ׃

And I have led you forty years in the wilderness; your clothes did not get old upon you, and your shoe did not get old upon your foot.

From this verse. it seems that they wore shoes for 40 years in the desert. This seems to contradict what Rash"i says in the earlier verse.

So which was it?

Answer 1

Ikar Siftei Hachamim on Deuteronomy 8:4:2 (excerpt):

ואם תאמר והא בפרשת כי תבא כתיב ונעלך לא בלתה מעל רגלך שמע מיניה שהיו להם מנעלים ויש לומר דהתם קאי איוצאי מצרים שהיו להם מנעלים אותם מנעלים לא בלו מעל רגליהם ומה שפירש כאן היינו אותן שנולדו במדבר שלא היו להם מנעלים.

(My translation):

If you would say that in parshat Ki Tavo it says, "Your shoes did not wear out from on your feet", we learn from this that they had shoes!

Thus, we must say that there (in Ki Tavo), it refers to those that left Egypt, that they had shoes, and those that had shoes, it says that the shoes did not wear out. Here (parshat Ekev) it is referring to those that were born in the desert that did not have shoes.