BackTrack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 78. Subsets\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array nums of unique elements, return all possible subsets (the power set).\n",
    "\n",
    "The solution set must not contain duplicate subsets. Return the solution in any order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [1,2,3,4]\n",
    "# Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subsets(nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        subset = nums\n",
    "        output = [[]]\n",
    "        \n",
    "        for num in nums:\n",
    "            output += [curr + [num] for curr in output]\n",
    "            print(output)\n",
    "        \n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [1]]\n",
      "[[], [1], [2], [1, 2]]\n",
      "[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]\n",
      "[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[],\n",
       " [1],\n",
       " [2],\n",
       " [1, 2],\n",
       " [3],\n",
       " [1, 3],\n",
       " [2, 3],\n",
       " [1, 2, 3],\n",
       " [4],\n",
       " [1, 4],\n",
       " [2, 4],\n",
       " [1, 2, 4],\n",
       " [3, 4],\n",
       " [1, 3, 4],\n",
       " [2, 3, 4],\n",
       " [1, 2, 3, 4]]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subsets(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approach 3: Lexicographic (Binary Sorted) Subsets\n",
    "The idea is that we map each subset to a bitmask of length n, where 1 on the ith position in bitmask means the presence of nums[i] in the subset, and 0 means its absence.\n",
    "\n",
    "For instance, the bitmask 0..00 (all zeros) corresponds to an empty subset, and the bitmask 1..11 (all ones) corresponds to the entire input array nums.\n",
    "\n",
    "Hence to solve the initial problem, we just need to generate n bitmasks from 0..00 to 1..11.\n",
    "\n",
    "It might seem simple at first glance to generate binary numbers, but the real problem here is how to deal with zero left padding, because one has to generate bitmasks of fixed length, i.e. 001 and not just 1. For that one could use standard bit manipulation trick:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nth_bit = 1 << n\n",
    "for i in range(2**n):\n",
    "    # generate bitmask, from 0..00 to 1..11\n",
    "    bitmask = bin(i | nth_bit)[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(2**n, 2**(n + 1)):\n",
    "    # generate bitmask, from 0..00 to 1..11\n",
    "    bitmask = bin(i)[3:]"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Generate all possible binary bitmasks of length n.\n",
    "\n",
    "Map a subset to each bitmask: 1 on the ith position in bitmask means the presence of nums[i] in the subset, and 0 means its absence.\n",
    "\n",
    "Return output list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        output = []\n",
    "        \n",
    "        for i in range(2**n, 2**(n + 1)):\n",
    "            # generate bitmask, from 0..00 to 1..11\n",
    "            bitmask = bin(i)[3:]\n",
    "            \n",
    "            # append subset corresponding to that bitmask\n",
    "            output.append([nums[j] for j in range(n) if bitmask[j] == '1'])\n",
    "        \n",
    "        return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 90. Subsets II\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array nums that may contain duplicates, return all possible subsets (the power set).\n",
    "\n",
    "The solution set must not contain duplicate subsets. Return the solution in any order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subsetsWithDup(nums: List[int]) -> List[List[int]]:\n",
    "    n = len(nums)\n",
    "\n",
    "    subset = nums\n",
    "    output = [[]]\n",
    "\n",
    "    for num in nums:\n",
    "#         for curr in output:\n",
    "#             if curr+[num] not in output:\n",
    "#                 output += curr+[num]\n",
    "        output += [curr+[num] for curr in output]\n",
    "    result = []\n",
    "    for item in output:\n",
    "        item = tuple(item)\n",
    "        if item not in result:\n",
    "            result.append(item)\n",
    "#     output = set(output)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [1,2,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(), (1,), (2,), (1, 2), (2, 2), (1, 2, 2)]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subsetsWithDup(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subsetsWithDup(nums):\n",
    "    ret = []\n",
    "    dfs(sorted(nums), [], ret)\n",
    "    return ret\n",
    "\n",
    "def dfs(nums, path, ret):\n",
    "    ret.append(path)\n",
    "    for i in range(len(nums)):\n",
    "        if i > 0 and nums[i] == nums[i-1]:\n",
    "            continue\n",
    "        dfs(nums[i+1:], path+[nums[i]], ret)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 368. Largest Divisible Subset\n",
    "\n",
    "Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:\n",
    "\n",
    "answer[i] % answer[j] == 0, or\n",
    "answer[j] % answer[i] == 0\n",
    "If there are multiple solutions, return any of them.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "    nums.sort()  # Sort the numbers\n",
    "    n = len(nums)\n",
    "    memo = {} \n",
    "    # Recursive function to find the largest divisible subset ending with the current element\n",
    "    def dfs(index, prev_index):\n",
    "        if index == n:\n",
    "            return []\n",
    "        if (index, prev_index) in memo:\n",
    "            return memo[(index, prev_index)]\n",
    "        best_subset = dfs(index + 1, prev_index)\n",
    "        # Include the current number if it is divisible by the last number in the subset\n",
    "        if prev_index == -1 or nums[index] % nums[prev_index] == 0:\n",
    "            subset_with_current = dfs(index + 1, index) + [nums[index]]\n",
    "            if len(subset_with_current) > len(best_subset):\n",
    "                best_subset = subset_with_current\n",
    "        memo[(index, prev_index)] = best_subset\n",
    "        return best_subset\n",
    "    largest_subset = dfs(0, -1)\n",
    "    return largest_subset  # Reverse to maintain the sorted order\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def largestDivisibleSubset(self, nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    # The container that holds all intermediate solutions.\n",
    "    # key: the largest element in a valid subset.\n",
    "    subsets = {-1: set()}\n",
    "\n",
    "    for num in sorted(nums):\n",
    "        subsets[num] = max([subsets[k] for k in subsets if num % k == 0], key=len) | {num}\n",
    "\n",
    "    return list(max(subsets.values(), key=len))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # DP array to store the size of the largest divisible subset that ends with nums[i]\n",
    "        dp = [1] * n\n",
    "        # Parent array to reconstruct the solution path\n",
    "        parent = [-1] * n\n",
    "        # Variables to track the maximum subset size and its last element's index\n",
    "        max_size, max_index = 1, 0\n",
    "        \n",
    "        # Fill dp and parent arrays\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:\n",
    "                    dp[i] = dp[j] + 1\n",
    "                    parent[i] = j\n",
    "                    if dp[i] > max_size:\n",
    "                        max_size, max_index = dp[i], i\n",
    "        \n",
    "        # Reconstruct the subset\n",
    "        answer = []\n",
    "        current = max_index\n",
    "        while current >= 0:\n",
    "            answer.append(nums[current])\n",
    "            current = parent[current]\n",
    "        \n",
    "        # Return the subset in reversed order to match the sorted order of nums\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1774. Closest Dessert Cost\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:\n",
    "\n",
    "There must be exactly one ice cream base.\n",
    "You can add one or more types of topping or have no toppings at all.\n",
    "There are at most two of each type of topping."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10\n",
    "Output: 10\n",
    "Explanation: Consider the following combination (all 0-indexed):\n",
    "- Choose base 1: cost 7\n",
    "- Take 1 of topping 0: cost 1 x 3 = 3\n",
    "- Take 0 of topping 1: cost 0 x 4 = 0\n",
    "Total: 7 + 3 + 0 = 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.toppings = [0]\n",
    "        \n",
    "    def closestCost(self, baseCosts, toppingCosts, target):\n",
    "        self.knapsack(toppingCosts, 0, 0, target)\n",
    "        possibilities = [[b + t, abs(target-(b+t))] for b in baseCosts for t in self.toppings ]        \n",
    "        possibilities.sort(key=lambda x: [x[1], x[0]])\n",
    "        return possibilities.pop(0)[0]\n",
    "    \n",
    "    def knapsack(self, tc, i, total, target):\n",
    "        if i == len(tc):\n",
    "            self.toppings.append(total)\n",
    "            return \n",
    "        self.knapsack(tc, i+1, total + 2*tc[i], target)\n",
    "        self.knapsack(tc, i+1, total+tc[i], target)\n",
    "        self.knapsack(tc, i+1, total, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "\tdef closestCost(self, baseCosts, toppingCosts, target):\n",
    "\t\t\"\"\"\n",
    "\t\t:type baseCosts: List[int]\n",
    "\t\t:type toppingCosts: List[int]\n",
    "\t\t:type target: int\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\t\tself.ans = float('inf')\n",
    "\t\ttoppingCosts.sort()\n",
    "\t\tfor base in baseCosts:\n",
    "\t\t\tself.dfs(toppingCosts, target, base)\n",
    "\t\treturn self.ans\n",
    "\n",
    "\tdef dfs(self, topping, target, sums):\n",
    "\t\tif abs(target - sums) < abs(self.ans - target):\n",
    "\t\t\tself.ans = sums\n",
    "\t\tif sums > target: return \n",
    "\t\tfor i in range(len(topping)):\n",
    "\t\t\tself.dfs(topping[i + 1:], target, sums + 0*topping[i])\n",
    "\t\t\tself.dfs(topping[i + 1:], target, sums + 1*topping[i])\n",
    "\t\t\tself.dfs(topping[i + 1:], target, sums + 2*topping[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "class Solution:\n",
    "    def closestCost(self, base, top, t):\n",
    "        top_combo = {0}\n",
    "        for x in top:\n",
    "            top_combo_next = copy.deepcopy(top_combo)\n",
    "            for y in top_combo:\n",
    "                top_combo_next.add(y+x)\n",
    "                top_combo_next.add(y+2*x)\n",
    "            top_combo = top_combo_next\n",
    "        \n",
    "        ans = dif = math.inf\n",
    "        for x in base:\n",
    "            for y in top_combo:\n",
    "                cost = x+y\n",
    "                cdif = abs(t-cost)\n",
    "                if cdif < dif:\n",
    "                    ans, dif = cost, cdif\n",
    "                elif cdif == dif and cost < ans:\n",
    "                    ans, dif = cost, cdif\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 991. Broken Calculator\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "There is a broken calculator that has the integer startValue on its display initially. In on operation you can:\n",
    "\n",
    "multiply the number on the display by 2, or\n",
    "subtract 1 from the number on the display.\n",
    "Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Intuition\n",
    "\n",
    "Instead of multiplying by 2 or subtracting 1 from X, we could divide by 2 (when Y is even) or add 1 to Y.\n",
    "\n",
    "The motivation for this is that it turns out we always greedily divide by 2:\n",
    "\n",
    "If say Y is even, then if we perform 2 additions and one division, we could instead perform one division and one addition for less operations [(Y+2) / 2 vs Y/2 + 1].\n",
    "\n",
    "If say Y is odd, then if we perform 3 additions and one division, we could instead perform 1 addition, 1 division, and 1 addition for less operations [(Y+3) / 2 vs (Y+1) / 2 + 1]."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "If X > Y, we do not have a lot of choice, we can just decrease X by one until it becomes equal to Y, so answer will be X - Y.\n",
    "If X == Y, then we already happy and we return 0.\n",
    "If Y % 2 == 1, then let us think, what can be the last step? It can not be multilication by 2, so the only choice is subtraction of 1 and on previous step we have configuration (X, Y + 1), for which we run our function recursively.\n",
    "If Y % 2 == 0, let us prove that we always need to divide by 2 in this case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Complexity: time complexity is O(log Y), because every two iteration number decreased at least twice. Space complexity here is also O(log Y), because we use recursion. It can be made O(1) if we do it iteratively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "    ans = 0\n",
    "    while target > startValue:\n",
    "        ans += 1\n",
    "        if target%2: target += 1\n",
    "        else: target //= 2\n",
    "\n",
    "    return ans + startValue-target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def brokenCalc(self, X, Y):\n",
    "        if X > Y: return X - Y\n",
    "        if X == Y: return 0\n",
    "        if Y % 2 == 0:\n",
    "            return self.brokenCalc(X, Y//2) + 1\n",
    "        else:\n",
    "            return self.brokenCalc(X, Y + 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "curr = [[3, 4], [3, 4], [3, 4], [3, 4], [3, 4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[3, 4], [3, 4], [3, 4], [3, 4], [3, 4]]\n"
     ]
    }
   ],
   "source": [
    "print(curr[0:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "https://leetcode.com/problems/combination-sum/discuss/429538/General-Backtracking-questions-solutions-in-Python-for-reference-%3A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 39. Combination Sum\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.\n",
    "\n",
    "The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.\n",
    "\n",
    "It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "#correct solution DP or backtrack\n",
    "def combinationSum(candidates, target):\n",
    "    candidates.sort()\n",
    "    dp = [[] for _ in range(target+1)]\n",
    "    for t in range(1, target+1):  #dp[t] saves all combinations have t sum\n",
    "        for i in candidates:\n",
    "            if i > t: \n",
    "                break   #from now on, all sum > t, break out\n",
    "            if i == t: \n",
    "                dp[t].append([i])\n",
    "                break  #the element value equals to current target t\n",
    "            #to ensure no duplicate, the later coming item should be strictly greater than previous ones, make the result an asc sequence. \n",
    "            dp[t].extend(path + [i] for path in dp[t-i] if i >= path[-1])\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 377. Combination Sum IV\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "    # minor optimization\n",
    "    # nums.sort()\n",
    "    dp = [0 for i in range(target+1)]\n",
    "    dp[0] = 1\n",
    "\n",
    "    for comb_sum in range(target+1):\n",
    "\n",
    "        for num in nums:\n",
    "            if comb_sum - num >= 0:\n",
    "                dp[comb_sum] += dp[comb_sum-num]\n",
    "            # minor optimization, early stopping.\n",
    "            # else:\n",
    "            #     break\n",
    "    return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "    @lru_cache(maxsize = None)\n",
    "    def combs(remain):\n",
    "        if remain == 0:\n",
    "            return 1\n",
    "\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            if remain - num >= 0:\n",
    "                result += combs(remain - num)\n",
    "            # potential optimization\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return result\n",
    "\n",
    "    return combs(target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 51. N-Queens\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.\n",
    "\n",
    "Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.\n",
    "\n",
    "Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solveNQueens(n: int) -> List[List[str]]:\n",
    "    def init_board(state):\n",
    "        board = []\n",
    "        for row in state:\n",
    "            board.append(\"\".join(row))\n",
    "        return board\n",
    "\n",
    "    def backtrack(row, diagonals, anti_diagonals, cols, state):\n",
    "        # print(row, state)\n",
    "        # Base case - N queens have been placed\n",
    "        if row == n:\n",
    "            ans.append(init_board(state))\n",
    "            return\n",
    "\n",
    "        for col in range(n):\n",
    "            curr_diagonal = row - col\n",
    "            curr_anti_diagonal = row + col\n",
    "            # If the queen is not placeable\n",
    "            if (col in cols or curr_diagonal in diagonals or curr_anti_diagonal in anti_diagonals):\n",
    "                continue\n",
    "                \n",
    "            # \"Add\" the queen to the board\n",
    "            cols.add(col)\n",
    "            diagonals.add(curr_diagonal)\n",
    "            anti_diagonals.add(curr_anti_diagonal)\n",
    "            state[row][col] = 'Q'\n",
    "            \n",
    "            # Move on to the next row with the updated board state\n",
    "            backtrack(row + 1, diagonals, anti_diagonals, cols, state)\n",
    "\n",
    "            # \"Remove\" the queen from the board since we have already\n",
    "            # explored all valid paths using the above function call\n",
    "            cols.remove(col)\n",
    "            diagonals.remove(curr_diagonal)\n",
    "            anti_diagonals.remove(curr_anti_diagonal)\n",
    "            state[row][col] = '.'\n",
    "\n",
    "    ans = []\n",
    "    empty_board = [['.'] *n for _ in range(n)]\n",
    "    backtrack(0, set(), set(), set(), empty_board)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Q....', '..Q..', '....Q', '.Q...', '...Q.'],\n",
       " ['Q....', '...Q.', '.Q...', '....Q', '..Q..'],\n",
       " ['.Q...', '...Q.', 'Q....', '..Q..', '....Q'],\n",
       " ['.Q...', '....Q', '..Q..', 'Q....', '...Q.'],\n",
       " ['..Q..', 'Q....', '...Q.', '.Q...', '....Q'],\n",
       " ['..Q..', '....Q', '.Q...', '...Q.', 'Q....'],\n",
       " ['...Q.', 'Q....', '..Q..', '....Q', '.Q...'],\n",
       " ['...Q.', '.Q...', '....Q', '..Q..', 'Q....'],\n",
       " ['....Q', '.Q...', '...Q.', 'Q....', '..Q..'],\n",
       " ['....Q', '..Q..', 'Q....', '...Q.', '.Q...']]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solveNQueens(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 332. Reconstruct Itinerary\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.\n",
    "\n",
    "All of the tickets belong to a man who departs from \"JFK\", thus, the itinerary must begin with \"JFK\". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.\n",
    "\n",
    "For example, the itinerary [\"JFK\", \"LGA\"] has a smaller lexical order than [\"JFK\", \"LGB\"].\n",
    "You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Approach 1: Backtracking + Greedy\n",
    "Intuition\n",
    "\n",
    "As common strategies for problems of graph traversal, we often apply the methodologies of backtracking or greedy. As it turns out, we can apply both of them for this problem.\n",
    "\n",
    "Typically, backtracking is used to enumerate all possible solutions for a problem, in a trial-fail-and-fallback strategy.\n",
    "\n",
    "At each airport, one might have several possible destinations to fly to. With backtracking, we enumerate each possible destination. We mark the choice at each iteration (i.e. trial) before we move on to the chosen destination. If the destination does not lead to a solution (i.e. fail), we would then fallback to the previous state and start another iteration of trial-fail-and-fallback cycle.\n",
    "\n",
    "A greedy algorithm is any algorithm that follows the problem-solving heuristic of making locally optimal choice at each step, with the intent of reaching the global optimum at the end.\n",
    "\n",
    "As suggested by its definition, a greedy algorithm does not necessarily lead to a globally optimal solution, but rather a reasonable approximation in exchange of less computing time.\n",
    "\n",
    "Nonetheless, sometimes it is the way to produce a global optimum for certain problems. This is the case for this problem as well.\n",
    "\n",
    "At each airport, given a list of possible destinations, while backtracking, at each step we would pick the destination greedily in lexical order, i.e. the one with the smallest lexical order would have its trial first.\n",
    "\n",
    "With this greedy strategy, we would ensure that the final solution that we find would have the smallest lexical order, because all other solutions that have smaller lexical order have been trialed and failed during the process of backtracking.\n",
    "\n",
    "Algorithm\n",
    "\n",
    "Here we explain how we implement a solution for this problem, by combining the strategies of backtracking and greedy.\n",
    "\n",
    "As the first step, we build a graph data structure from the given input. This graph should allow us to quickly identify a list of potential destinations, given an origin. Here we adopted the hashmap (or dictionary) data structure, with each entry as <origin, [destinations]>.\n",
    "\n",
    "Then due to our greedy strategy, we then should order the destination list for each entry in lexical order. As an alternative solution, one could use PriorityQueue data structure in the first step to keep the list of destinations, which would maintain the order at the moment of constructing the list.\n",
    "\n",
    "As the final step, we kick off the backtracking traversal on the above graph, to obtain the final result.\n",
    "\n",
    "At the beginning of the backtracking function, as the bottom case, we check if we have already obtained a valid itinerary.\n",
    "\n",
    "Otherwise, we enumerate the next destinations in order.\n",
    "\n",
    "We mark the status of visit, before and after each backtracking loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findItinerary(tickets: List[List[str]]) -> List[str]:\n",
    "    flightMap = {}\n",
    "    for ticket in tickets:\n",
    "        origin , dest = ticket[0], ticket[1]\n",
    "        flightMap[origin] = dest\n",
    "    print(flightMap)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "tickets = [[\"MUC\",\"LHR\"],[\"JFK\",\"MUC\"],[\"SFO\",\"SJC\"],[\"LHR\",\"SFO\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "tickets2= [[\"JFK\",\"SFO\"],[\"JFK\",\"ATL\"],[\"SFO\",\"ATL\"],[\"ATL\",\"JFK\"],[\"ATL\",\"SFO\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'SFO': ['SJC'], 'MUC': ['LHR'], 'LHR': ['SFO'], 'JFK': ['MUC']}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['JFK', 'MUC', 'LHR', 'SFO', 'SJC']"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findItinerary(tickets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### backtracking and improve it to be iterative answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findItinerary(tickets):\n",
    "    targets = collections.defaultdict(list)\n",
    "    for a, b in sorted(tickets)[::-1]:\n",
    "        targets[a] += b,\n",
    "    route = []\n",
    "    def visit(airport):\n",
    "        while targets[airport]:\n",
    "            visit(targets[airport].pop())\n",
    "        route.append(airport)\n",
    "    visit('JFK')\n",
    "    return route[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findItinerary(tickets):\n",
    "    targets = collections.defaultdict(list)\n",
    "    for a, b in sorted(tickets)[::-1]:\n",
    "        targets[a] += b,\n",
    "    route, stack = [], ['JFK']\n",
    "    while stack:\n",
    "        while targets[stack[-1]]:\n",
    "            stack += targets[stack[-1]].pop(),\n",
    "        route += stack.pop(),\n",
    "    return route[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findItinerary(tickets: List[List[str]]) -> List[str]:\n",
    "    targets = {}\n",
    "    for origin, dest in sorted(tickets)[::-1]:\n",
    "        # targets[origin].append(dest)\n",
    "        targets.setdefault(origin, []).append(dest)\n",
    "    print(targets)\n",
    "    route = []\n",
    "    def visit(airport):\n",
    "        if airport in targets:\n",
    "            while(targets[airport]):\n",
    "                visit(targets[airport].pop())\n",
    "        route.append(airport)\n",
    "    visit('JFK')\n",
    "    return(route[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'SFO': ['ATL'], 'JFK': ['SFO', 'ATL'], 'ATL': ['SFO', 'JFK']}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findItinerary(tickets2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 46. Permutations\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array nums of ##distinct## integers, return all the possible permutations. You can return the answer in any order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "    def backtracking(res,visited,subset,nums):\n",
    "        if len(subset) == len(nums):\n",
    "            res.append(subset)\n",
    "        for i in range(len(nums)):\n",
    "            if i not in visited:\n",
    "                visited.add(i)\n",
    "                backtracking(res,visited,subset+[nums[i]],nums)\n",
    "                visited.remove(i)\n",
    "\n",
    "    visited = set()\n",
    "    res = []\n",
    "    backtracking(res,visited,[],nums)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "    def dfs(nums, path, res):\n",
    "        if not nums:\n",
    "            res.append(path)\n",
    "            # return # backtracking\n",
    "        for i in range(len(nums)):\n",
    "            dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)\n",
    "\n",
    "    res = []\n",
    "    dfs(nums, [], res)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 47. Permutations II\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a collection of numbers, nums, that might *contain duplicates*, return all possible unique permutations in any order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "    def dfs(nums, visited, path, res):\n",
    "        if len(nums) == len(path):\n",
    "            res.append(path)\n",
    "            return \n",
    "        for i in range(len(nums)):\n",
    "            if not visited[i]: \n",
    "                if i>0 and not visited[i-1] and nums[i] == nums[i-1]:  # here should pay attention\n",
    "                    continue\n",
    "                visited[i] = True\n",
    "                dfs(nums, visited, path+[nums[i]], res)\n",
    "                visited[i] = False\n",
    "    res, visited = [], [False]*len(nums)\n",
    "    nums.sort()\n",
    "    dfs(nums, visited, [], res)\n",
    "    return res\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "    results = []\n",
    "    def backtrack(comb, counter):\n",
    "        if len(comb) == len(nums):\n",
    "            # make a deep copy of the resulting permutation,\n",
    "            # since the permutation would be backtracked later.\n",
    "            results.append(list(comb))\n",
    "            return\n",
    "\n",
    "        for num in counter:\n",
    "            if counter[num] > 0:\n",
    "                # add this number into the current combination\n",
    "                comb.append(num)\n",
    "                counter[num] -= 1\n",
    "                # continue the exploration\n",
    "                backtrack(comb, counter)\n",
    "                # revert the choice for the next exploration\n",
    "                comb.pop()\n",
    "                counter[num] += 1\n",
    "\n",
    "    backtrack([], Counter(nums))\n",
    "\n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1220. Count Vowels Permutation\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Given an integer n, your task is to count how many strings of length n can be formed under the following rules:\n",
    "\n",
    "Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')\n",
    "Each vowel 'a' may only be followed by an 'e'.\n",
    "Each vowel 'e' may only be followed by an 'a' or an 'i'.\n",
    "Each vowel 'i' may not be followed by another 'i'.\n",
    "Each vowel 'o' may only be followed by an 'i' or a 'u'.\n",
    "Each vowel 'u' may only be followed by an 'a'.\n",
    "Since the answer may be too large, return it modulo 10^9 + 7.\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countVowelPermutation(self, n: int) -> int:\n",
    "    a_vowel_permutation_count = [1] * n\n",
    "    e_vowel_permutation_count = [1] * n\n",
    "    i_vowel_permutation_count = [1] * n\n",
    "    o_vowel_permutation_count = [1] * n\n",
    "    u_vowel_permutation_count = [1] * n\n",
    "    MOD = 10 ** 9 + 7\n",
    "    for i in range(1, n):\n",
    "        a_vowel_permutation_count[i] = (e_vowel_permutation_count[i - 1] + i_vowel_permutation_count[i - 1] + u_vowel_permutation_count[i - 1]) % MOD\n",
    "        e_vowel_permutation_count[i] = (a_vowel_permutation_count[i - 1] + i_vowel_permutation_count[i - 1]) % MOD\n",
    "        i_vowel_permutation_count[i] = (e_vowel_permutation_count[i - 1] + o_vowel_permutation_count[i - 1]) % MOD\n",
    "        o_vowel_permutation_count[i] = (i_vowel_permutation_count[i - 1]) % MOD\n",
    "        u_vowel_permutation_count[i] = (i_vowel_permutation_count[i - 1] + o_vowel_permutation_count[i - 1]) % MOD\n",
    "    result = 0\n",
    "    result = (a_vowel_permutation_count[n - 1] + e_vowel_permutation_count[n - 1] + \n",
    "              i_vowel_permutation_count[n - 1] + o_vowel_permutation_count[n - 1] + \n",
    "              u_vowel_permutation_count[n - 1]) % MOD\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countVowelPermutation(self, n: int) -> int:\n",
    "    # initialize the number of strings ending with a, e, i, o, u\n",
    "    a_count = e_count = i_count = o_count = u_count = 1\n",
    "    MOD = 10 ** 9 + 7\n",
    "\n",
    "    for i in range(1, n):\n",
    "        a_count_new = (e_count + i_count + u_count) % MOD\n",
    "        e_count_new = (a_count + i_count) % MOD\n",
    "        i_count_new = (e_count + o_count) % MOD\n",
    "        o_count_new = (i_count) % MOD\n",
    "        u_count_new = (i_count + o_count) % MOD\n",
    "\n",
    "        # https://docs.python.org/3/reference/expressions.html#evaluation-order\n",
    "        a_count, e_count, i_count, o_count, u_count = \\\n",
    "            a_count_new, e_count_new, i_count_new, o_count_new, u_count_new\n",
    "\n",
    "    return (a_count + e_count + i_count + o_count + u_count) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countVowelPermutation(self, n: int) -> int:\n",
    "    # initialize the number of strings ending with a, e, i, o, u\n",
    "    MOD = 10 ** 9 + 7\n",
    "    @functools.cache\n",
    "    def vowel_permutation_count(i, vowel):\n",
    "        total = 1\n",
    "        if i > 1:\n",
    "            if vowel == 'a':\n",
    "                total = (vowel_permutation_count(i - 1, 'e') + vowel_permutation_count(i - 1, 'i') + vowel_permutation_count(i - 1, 'u')) % MOD\n",
    "            elif vowel == 'e':\n",
    "                total = (vowel_permutation_count(i - 1, 'a') + vowel_permutation_count(i - 1, 'i')) % MOD\n",
    "            elif vowel == 'i':\n",
    "                total = (vowel_permutation_count(i - 1, 'e') + vowel_permutation_count(i - 1, 'o')) % MOD\n",
    "            elif vowel == 'o':\n",
    "                total = vowel_permutation_count(i - 1, 'i')\n",
    "            else:\n",
    "                total = (vowel_permutation_count(i - 1, 'i') + vowel_permutation_count(i - 1, 'o')) % MOD\n",
    "        return total\n",
    "    return sum(vowel_permutation_count(n, vowel) for vowel in 'aeiou') % MOD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 79. Word Search\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an m x n grid of characters board and a string word, return true if word exists in the grid.\n",
    "\n",
    "The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "    \"\"\"\n",
    "    :type board: List[List[str]]\n",
    "    :type word: str\n",
    "    :rtype: bool\n",
    "    \"\"\"\n",
    "    self.ROWS = len(board)\n",
    "    self.COLS = len(board[0])\n",
    "    self.board = board\n",
    "\n",
    "    for row in range(self.ROWS):\n",
    "        for col in range(self.COLS):\n",
    "            if self.backtrack(row, col, word):\n",
    "                return True\n",
    "\n",
    "    # no match found after all exploration\n",
    "    return False\n",
    "\n",
    "def backtrack(self, row, col, suffix):\n",
    "    \"\"\"\n",
    "        backtracking with side-effect,\n",
    "           the matched letter in the board would be marked with \"#\".\n",
    "    \"\"\"\n",
    "    # bottom case: we find match for each letter in the word\n",
    "    if len(suffix) == 0:\n",
    "        return True\n",
    "\n",
    "    # Check the current status, before jumping into backtracking\n",
    "    if row < 0 or row == self.ROWS or col < 0 or col == self.COLS \\\n",
    "            or self.board[row][col] != suffix[0]:\n",
    "        return False\n",
    "\n",
    "    # mark the choice before exploring further.\n",
    "    self.board[row][col] = '#'\n",
    "    # explore the 4 neighbor directions\n",
    "    for rowOffset, colOffset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:\n",
    "        # sudden-death return, no cleanup.\n",
    "        if self.backtrack(row + rowOffset, col + colOffset, suffix[1:]):\n",
    "            return True\n",
    "\n",
    "    # revert the marking\n",
    "    self.board[row][col] = suffix[0]\n",
    "\n",
    "    # Tried all directions, and did not find any match\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# 1239. Maximum Length of a Concatenated String with Unique Characters\n",
    "You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.\n",
    "\n",
    "Return the maximum possible length of s.\n",
    "\n",
    "A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxLength(self, arr: List[str]) -> int:\n",
    "    def isUnique(s):\n",
    "        return len(s) == len(set(s))\n",
    "\n",
    "    def backtrack(index, current):\n",
    "        if index == len(arr) and isUnique(current):\n",
    "            return len(current)\n",
    "        if index == len(arr):\n",
    "            return 0\n",
    "        # Include the current element\n",
    "        included = 0\n",
    "        if isUnique(current + arr[index]):\n",
    "            included = backtrack(index + 1, current + arr[index])\n",
    "        # Exclude the current element\n",
    "        excluded = backtrack(index + 1, current)\n",
    "        return max(included, excluded)\n",
    "\n",
    "    return backtrack(0, \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxLength(self, arr: List[str]) -> int:\n",
    "    def dfs(arr, pos, res):\n",
    "        if len(res) != len(set(res)):\n",
    "            return 0\n",
    "        best = len(res)\n",
    "        for i in range(pos, len(arr)):\n",
    "            best = max(best, dfs(arr, i+1, res+arr[i]))\n",
    "        return best\n",
    "    return dfs(arr, 0, \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = [\"\"]\n",
    "best = 0\n",
    "for word in arr:\n",
    "    # We only want to iterate through results\n",
    "    # that existed prior to this loop\n",
    "    for i in range(len(results)):\n",
    "        # Form a new result combination and\n",
    "        # use a set to check for duplicate characters\n",
    "        new_res = results[i] + word\n",
    "        if len(new_res) != len(set(new_res)):\n",
    "            continue\n",
    "\n",
    "        # Add valid options to results and\n",
    "        # keep track of the longest so far\n",
    "        results.append(new_res)\n",
    "        best = max(best, len(new_res))\n",
    "return best"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1601 Maximum Number of Achievable Transfer Requests\n",
    "\n",
    "We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It's transfer season, and some employees want to change the building they reside in.\n",
    "\n",
    "You are given an array requests where requests[i] = [fromi, toi] represents an employee's request to transfer from building fromi to building toi.\n",
    "\n",
    "All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.\n",
    "\n",
    "Return the maximum number of achievable requests.\n",
    "\n",
    "#### GPT4 could do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "    def backtrack(i, buildings):\n",
    "        if i == len(requests):\n",
    "            if all(b == 0 for b in buildings):\n",
    "                return 0\n",
    "            return float('-inf')\n",
    "        ans = backtrack(i+1, buildings)\n",
    "        buildings[requests[i][0]] -=1\n",
    "        buildings[requests[i][1]] +=1\n",
    "        ans = max(ans, 1+ backtrack(i+1, buildings))\n",
    "        buildings[requests[i][0]] +=1\n",
    "        buildings[requests[i][1]] -=1\n",
    "\n",
    "        return ans\n",
    "    return backtrack(0, [0]*n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "    for k in range(1, len(requests) + 1):\n",
    "            for subset in combinations(requests, k):\n",
    "                buildings = [0] * n\n",
    "\n",
    "                for request in subset:\n",
    "                    buildings[request[0]] -= 1  # Employee leaving\n",
    "                    buildings[request[1]] += 1  # Employee arriving\n",
    "\n",
    "                if all(b == 0 for b in buildings):\n",
    "                    max_requests = max(max_requests, k)\n",
    "\n",
    "        return max_requests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2305. Fair Distribution of Cookies\n",
    "You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.\n",
    "\n",
    "The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.\n",
    "\n",
    "Return the minimum unfairness of all distributions.\n",
    "\n",
    "#### GPT4 cannot do it yet, since it's not trained on it yet.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        curr = [0] *k \n",
    "        n = len(cookies)\n",
    "        def dfs(i, zero_count):\n",
    "            if n-i < zero_count:\n",
    "                return float('inf')\n",
    "            if i == n:\n",
    "                return max(curr)\n",
    "\n",
    "            ans = float('inf')\n",
    "            for j in range(k):\n",
    "                zero_count -= int(curr[j]==0)\n",
    "                curr[j] += cookies[i]\n",
    "                ans = min(ans, dfs(i+1, zero_count))\n",
    "                curr[j] -= cookies[i]\n",
    "                zero_count += int(curr[j]==0)\n",
    "            return ans\n",
    "        return dfs(0, k)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}