0-1 Knapsack | Tricky but intresting 🤯
Intuition\nLol, I was explaining my classmate what knapsack problem is and when i saw this problem I was like, Hmm we either consider to keep track of one arr e
# Intuition\nLol, I was explaining my classmate what knapsack problem is and when i saw this problem I was like, Hmm we either consider to keep track of one `arr` element to add in `subsequence` or we don\'t, isnt it `0-1 Knapsack`.\n\nThen i saw the constraints, `0-1 Knapsack` looked feasible.\n\n# Approach\nWe either,\n- Don\'t choose the current ele of `arr`,\n    Our subsequnce remains same but we go to next element\n    `dfs(i + 1, seen)`\n- We choose current ele of `arr` and add it to subsequence,\n    `len(arr[i]) + dfs(i + 1, seen | set(arr[i]))`, `|` add the two sets\n    Rules,\n    - The ele itself should have unique characters,\n        `currSeen = set()` keeps track of it\n    - The ele characters should not be in the `knapsack` i.e, `seen`\n    - If any of the two rules are broken we `return notIncluded`.\n        Why? breaking the rules means we cannot include the ele, and where do we have the answer for that case? `notIncluded`.\nWhich ever of these two cases gives us the maximum `knapsack` we go with it.\n\n# Complexity\n- Time complexity: `O(2 ^ n)`\n    - Maximum Recursion Branch : `2`\n    - Maximum Recursion Depth : `n` = length of arr\n    - Maximum Comparision in each Recursive call : `26`\n\n- Space complexity: `O(1)`\n    - `seen` has unique elements => `max(len(seen)) = 26`\n    - `currSeen` has unique elements => `max(len(currSeen)) = 26`\n\n# Code\n```\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        def dfs(i, seen):\n            if i >= len(arr):\n                return 0\n\n            notIncluded = dfs(i + 1, seen)\n\n            currSeen = set()\n            for c in arr[i]:\n                if c in seen or c in currSeen:\n                    return notIncluded\n                currSeen.add(c)\n\n            included = len(arr[i]) + dfs(i + 1, seen | set(arr[i]))\n\n            return max(notIncluded, included)\n        \n        return dfs(0, set())\n\n```
['Python3']