Sorting + Preprocessing + DFS Speed up DFS to squeeze by weird time cutoff
Given n <= 20, iterating all possible subsets and checking for violations seem reasonable, but checking each pair for every subset results in a complexity of O(
Given n <= 20, iterating all possible subsets and checking for violations seem reasonable, but checking each pair for every subset results in a complexity of O(2^n * n ^ 2). Which TLE\'s when n == 19.\n\nSubsequently, we might instead try DFS, which not only prunes many incorrect subsets, when adding an element to existing valid subset, we only need to check up to n other elements. Which has complexity  O(2^n * n), which TLE\'s when n == 20.\n\nLastly, we can take advantage of the property of difference, using sorting and preprocessing to achieve near constant time when adding new elements to a valid subset. O(2^n * max banned range). \nThe given testsets seem to have all unique values which means that max banned range == 1. O(2^n) passes all test cases\n# Code\n```\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        banned_range = []\n        n = len(nums)\n        for i in range(len(nums)):\n            l = 100\n            r = -1\n            for j in range(0,i):\n                if nums[i] == nums[j] + k:\n                    l = min(l,j)\n                    r = max(r,j)\n            banned_range.append([l,r])\n        \n        tot = [0]\n        def dfs(l):\n            if n == len(l):\n                return\n            else:\n                left,right = banned_range[len(l)]\n                if not any(l[left:right + 1]):\n                    tot[0] += 1\n                    dfs(l + [True])         \n                dfs(l + [False])\n        dfs([])\n        return tot[0] \n                    \n```
['Python3']