# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: 'Python 3.7.6 64-bit (''vela'': pipenv)'
#     language: python
#     name: python37664bitvelapipenvde09592071074af6a70ce3b1ce38af95
# ---

# # 2021-05-08 Daily Practice
#
# - [x] Practice
#   - [ ] SQL
#   - [x] Algorithms + Data Structures
#   - [ ] Solve + Design
# - [ ] Learn
# - [ ] Write
# - [ ] Build

# ---
#
# ## Practice

# ### Combination Sum
#
# > [On LeetCode](https://leetcode.com/problems/combination-sum/)
#
# 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.
#
# 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.
#
# It is guaranteed that the number of unique combinations that sum up to `target` is less than 150 combinations for the given input.
#
# Example 1:
#
#     Input: candidates = [2,3,6,7], target = 7
#     Output: [[2,2,3],[7]]
#     Explanation:
#     2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
#     7 is a candidate, and 7 = 7.
#     These are the only two combinations.
#
# Example 2:
#
#     Input: candidates = [2,3,5], target = 8
#     Output: [[2,2,2,2],[2,3,3],[3,5]]
#
# Example 3:
#
#     Input: candidates = [2], target = 1
#     Output: []
#
# Example 4:
#
#     Input: candidates = [1], target = 1
#     Output: [[1]]
#
# Example 5:
#
#     Input: candidates = [1], target = 2
#     Output: [[1,1]]
#

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # Create a list to hold the chosen candidates
        # For each element in the array
        # If element is larger than target, do nothing
        # If element is equal to target, add single instance of element (as list) to chosen
        # If element is smaller than target...
        # # If target mod element is zero, then append list of n element where n = target / element
        # # If target mod element is nonzero, use result of floor division to find out how many times element goes into target
        # # Subtract result of floor division times element from target
        # ...nope, this isn't a good implementation


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # Create a list to hold the chosen candidates
        # For each element in the array
        # # If element is larger than target, do nothing
        # # If element is equal to target, add single instance of element (as list) to chosen
        # If element is smaller than target...
        # # Create list of chosen ones for this element; append one copy of element to this new list
        # # Subtract element from target, and compare again
        # -> This makes me think recursion!


# ```txt
# candidates = [2,3,6,7], target = 7
# element = 2
# element is smaller than target.
# chose = [2]
# new_target = 7 - 2 = 5
# element is smaller than target.
# chose = [2, 2]
# new_target = 5 - 2 = 3
# element is smaller than target.
# chose = [2, 2, 2]
# new target = 3 - 2 = 1
# element is larger than target.
# look for target in array
# ```

# Recursion?
#
# ```txt
# candidates = [2,3,6,7], target = 7
# Create a path to the target, using the remainder. Return path if it works, otherwise backtrack.
# ```

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        chosen = []  # List of paths to return
        sorted_cand = sorted(candidates)  # Ensure list of candidates is sorted

    def dfs(self, c, tgt):
        # Base case: target = 0 -> valid path found
        if tgt = 0:
            return [c[0]]
        # Base case: target < path[-1] -> invalid path; backtrack
        elif tgt < c[0]:
            return
        # Recursive case: candidates to search and new target
        valid = self.dfs(c, tgt - c[0])
        if valid is None:
            valid = self.dfs(c[1:], tgt - c[1])
        return [c[0]] + ...


# Not sure if it's possible without iteration.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        chosen = []  # List of paths to return
        sorted_cand = sorted(candidates)  # Ensure list of candidates is sorted

    def dfs(self, c, tgt):
        # Base case: target < path[-1] -> invalid path; backtrack
        elif tgt < 0: return
        # Base case: target = 0 -> valid path found
        if tgt = 0: return [c[0]]


# Solution from the discussion section
class Solution:
    def combinationSum(self, candidates, target):
        ret = []
        self.dfs(candidates, target, [], ret)
        return ret
    
    def dfs(self, nums, target, path, ret):
        if target < 0:
            return 
        if target == 0:
            ret.append(path)
            return 
        for i in range(len(nums)):
            self.dfs(nums[i:], target-nums[i], path+[nums[i]], ret)


# ### Buy and Sell Stock I
#
# > On [LeetCode](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min = prices[0]
        profit = 0
        for p in prices:
            if p < min: min = p
            if p - min > profit: profit = p - min
        return profit

StarcoderdataJupyterScriptsDedupFiltered