Python | Backtracking | Also generates the solution expressions
I was asked this question in a technical interview, with a slight variation--instead of a boolean, they wanted me to return a list of the expressions that would
I was asked this question in a technical interview, with a slight variation--instead of a boolean, they wanted me to return a list of the expressions that would reach the target number. This was my solution. The basic idea is:\n\n1. Since every operation is binary, you can partition the list of nums into two entities.\n2. Perform every possible arithmetic operation between those two entities.\n3. If an entity has multiple numbers in it, recurse within that entity.\n4. Repeat steps 1-3 with every possible binary partition of the list.\n\n```\nclass Solution:\n    def powerset(self, iterable):\n        """ powerset([1, 2, 3]) -> [1] [2] [3] [1, 2] [1, 3] [2, 3] """\n        s = list(iterable)\n        sets = chain.from_iterable(combinations(s, r) for r in range(1, len(s)))\n        return [list(tup) for tup in sets]\n\n    def getComplement(self, cards, subset):\n        c1 = Counter(cards)\n        c2 = Counter(subset)\n        return list((c1 - c2).elements())\n\n    def getOperations(self, left, right):\n        ans = []\n        for n1 in left:\n            for n2 in right:\n                ans.append(f\'({n1} + {n2})\')\n                ans.append(f\'({n1} - {n2})\')\n                ans.append(f\'({n1} * {n2})\')\n                ans.append(f\'({n2} - {n1})\')\n                if n2 != \'0\':\n                    ans.append(f\'({n1} / {n2})\')\n                if n1 != \'0\':\n                    ans.append(f\'({n2} / {n1})\')\n        return ans\n\n    def getPossibleAnswers(self, cards):\n        if len(cards) == 1:\n            return cards\n        else:\n            subsets = list(self.powerset(cards))\n            subsets = subsets[:len(subsets) // 2]  # Avoid duplicates\n            ans = []\n            for subset in subsets:\n                left = self.getPossibleAnswers(subset)\n                right = self.getPossibleAnswers(self.getComplement(cards, subset))\n                ans += self.getOperations(left, right)\n            return ans\n\n    def judgePoint24(self, cards: list[int]) -> list[str]:\n        possible = self.getPossibleAnswers(cards)\n        ans = []\n        for expression in possible:\n            try:\n                if round(eval(expression), 3) == 24:\n                    ans.append(expression)\n            except ZeroDivisionError:\n                pass\n        return ans\n```
['Backtracking', 'Python']