<jupyter_start><jupyter_text>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]]<jupyter_code>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!<jupyter_output><empty_output><jupyter_text>```txtcandidates = [2,3,6,7], target = 7element = 2element is smaller than target.chose = [2]new_target = 7 - 2 = 5element is smaller than target.chose = [2, 2]new_target = 5 - 2 = 3element is smaller than target.chose = [2, 2, 2]new target = 3 - 2 = 1element is larger than target.look for target in array``` Recursion?```txtcandidates = [2,3,6,7], target = 7Create a path to the target, using the remainder. Return path if it works, otherwise backtrack.```<jupyter_code>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]] + ...<jupyter_output><empty_output><jupyter_text>Not sure if it's possible without iteration.<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>Buy and Sell Stock I> On [LeetCode](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)<jupyter_code>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<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10598031794095382, 'fraction_numerical': 0.019114307342922028, 'mean_word_length': 2.83248730964467, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 30, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '292409', 'license': 'MIT', 'n_tokens_mistral': 1597, 'n_tokens_neox': 1520, 'n_words': 622, 'path': 'ds/practice/daily_practice/21-05/21-05-08-128-sat.ipynb', 'repo_name': 'tobias-fyi/vela', 'size': '5284'}