Balance scale weights
A lab balances a sample against calibration weights. weight_masses gives the weights in the drawer, in the order they lie there, and every mass is a distinct positive number of grams. The sample sits on the left pan. Each weight may go on the right pan, join the sample on the left, or stay in the drawer. A setup balances when the right pan total equals sample_mass plus the left pan total. Return every balancing setup as a string: the weights it uses, in drawer order, each carrying a plus sign on the right pan and a minus sign beside the sample, joined by single spaces, so "+9 -3" is nine grams on the right and three beside the sample. Walk the drawer from the first weight, trying the right pan, then the left, then leaving the weight behind, and list the setups in that order. Return an empty list when nothing balances. sample_mass is at least 1 and there are at most 10 weights.
list_weighing_setups(weight_masses: list[int], sample_mass: int) → list[str][[1,3,9],5]out["-1 -3 +9"][[1,2,3,4],5]out["+1 +4","-1 +2 +4","+2 +3","-2 +3 +4"][[4],3]out[]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[1,3,9],5]["-1 -3 +9"]not run yetsample[[1,2,3,4],5]["+1 +4","-1 +2 +4","+2 +3","-2 +3 +4"]not run yetsample[[4],3][]not run yetsample