The cheapest and by far the best solution on a desktop Mac.. since you are not carrying it around..is plug a portable USB drive into the back of it. I suggested portable not because you can carry it easily.. but because they are self powered over USB, is near to silent and will work faster and more reliably than any network backup. You can buy good size portable 2.5" drives up to 5TB now.. I would buy at least 2TB for best value. Seagate, WD, LaCie etc.
Some people note these drives can be less reliable than 3.5" desktop drives.. do check any model you select with a google search to see if they have a lot more feedback than they should.
If you are adamant in wanting network backup.. and you do still need a router.. the Gen5 AC model Time Capsule is still the cheapest solution. Apple will sell out the stock.. hopefully at considerable discount in the refubished store. I suggest this with some hesitation, as failure of the TC in the first 12months might see you out on a limb. It will be impossible for Apple to replace it.
So do you also need a new router? If that is the case there are a very small selection of routers that support Time Machine to USB port. I am trialling one now.. Asus RT-AC3200.. but any of the high end Asus. (Some Linksys some netgear.) It is NOT sufficiently reliable for me to say buy it (at least on Time Machine reliability so far it has not been great). It is excellent router.. hugely superior wireless to latest Apple offerings which are 6 year old designs. But I do think High Sierra is part of the problem and therefore recommend you run it with alternative backup software.. eg Carbon Copy Cloner.
Selection of hard disk is vitally important even if it is USB3 as some disks behave strangely. Talk to me if you really plan to go down this path.
Without the need for a new router.. this is expensive.
An even more expensive solution is a NAS.. recommend Synology. A few of us have been testing Synology NAS for TM over network.. and they work very well. Although other cheaper end units offer TM compatibility do a google search again for issues.. the cheap end units from WD and Seagate with sealed in disks are not great.
Synology is top of that heap and excellent choice. Expect to pay several hundred dollars all up.
To justify the cost you really need to use the Synology as file server, iTunes server, photo storage etc. Otherwise it is difficult to see the value for just TIme Machine.
Another Mac on the network can act as Time Machine server.. it is built into High Sierra so I guess Apple has been planning this for a while. If you have multiple Macs you can upgrade one to High Sierra and use it as network target.
If you need to buy a Mac for the job it comes out around the same price as the synology so think it through.
A 2012 mac mini is excellent machine for this job. Later Mini are too locked down.. and even under powered for the cheaper ones.
And finally cloud storage. Cloud is great for storage of your user files.. much less great for system files and applications that depend on Mac file system. Recovery is much more painful. Cost is high long term. Poor internet speeds will lead to long and frustrating backup sessions. Time Machine still lacks iCloud as target.. but as Apple slowly turn your 27" iMac into a glorified ipad I suspect cloud is their final destination.
Similar threads are popping up
Will Time machine backups, wireless and hard wired, be supported on 3rd party routers?