python 3 - backtracking + binary search
Intuition\nSort the input array.\n\nDo backtracking. To put nums[i] into state list, see if (nums[i] - k) exists in state list. If yes, then you skip it.\n\nSin
# Intuition\nSort the input array.\n\nDo backtracking. To put nums[i] into state list, see if (nums[i] - k) exists in state list. If yes, then you skip it.\n\nSince we sorted the input array, state list is also sorted. You can use binary search to optimize the searching time.\n\n# Approach\nbacktracking + binary search\n\n# Complexity\n- Time complexity:\nO(2^n x logn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nimport bisect\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        nums.sort()\n\n        def bt(i) -> None:\n            nonlocal ans\n            if i == len(nums):\n                if state:\n                    ans += 1\n                return\n\n            # keep\n            target = nums[i] - k # target must be < nums[i]\n            ind = bisect.bisect_left(state, target)\n            if not state or ind == len(state) or ( # in the last / empty state\n                state[ind] != target\n            ):\n                state.append(nums[i])\n                bt(i + 1)\n                state.pop()\n            \n            # skip\n            bt(i + 1)\n            \n        \n        state = []\n        ans = 0\n        bt(0)\n        return ans\n```
['Binary Search', 'Backtracking', 'Python3']