def solution(s, t):
    result = []
    for i in range(len(s)):
        if s[i] in t:
            coll = set()
            for j in range(i, len(s)):
                if s[j] in t:
                    coll.add(s[j])
                    if len(coll) == len(t):
                        result.append(s[i:j+1])
    if result:
        return min(result, key=len)
    
    return ""
    

#solution where you just take subset I and replace last return statement 
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

   
        subset = [] 
        result = [] 
        
        #i is index of subset 
        def dfs(i): 
            if i >= len(nums): 
                result.append(subset.copy())
                return 
            
            #decision to include nums[i]
            subset.append(nums[i])
            #this recursive call will be given filled subset 
            dfs(i + 1)
            
            #decision NOT to include nums[i] 
            subset.pop()
            #this recursive call will be given empty subset 
            dfs(i + 1)
        
        dfs(0) 
        
        #need to remove duplicate sublists within result 
        return ([list(i) for i in {*[tuple(sorted(i)) for i in result]}])  
  

#solution to prevent duplicates in the first place
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

   
        result = []
		nums.sort() 

		def backtrack(i, subset): 
        	if i == len(nums): 
            	res.append(subset.copy())
				return 
			
			#all subsets that include nums[i] 
            subset.append(nums[i]) 
			backtrack(i + 1, subset) 
			#remove number we just added 
            subset.pop()
            
            #all subsets that don't include nums[i]
        	while i + 1 < len(nums) and nums[i] == nums[i + 1]: 
            	i += 1 
			backtrack(i + 1, subset)
		
		backtrack(0, [])
		
		return result 
        
        
        
        
#solution for array with unique integer array. only last return line is dfferent 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset = [] 
        result = [] 
        
        #i is index of subset 
        def dfs(i): 
            if i >= len(nums): 
                result.append(subset.copy())
                return 
            
            #decision to include nums[i]
            subset.append(nums[i])
            #this recursive call will be given filled subset 
            dfs(i + 1)
            
            #decision NOT to include nums[i] 
            subset.pop()
            #this recursive call will be given empty subset 
            dfs(i + 1)
        
        dfs(0) 
        
        return result 
        
        
        

def solution(n, k):
    return climb(n, k, [])
    
        
        
def climb(n, k, jumps):
    if n == 0:
        return [jumps]
    
    out = []
    
    for i in range(1, k+1):
        if i > n:
            continue
            
        temp = jumps + [i] 
        out += climb(n-i, k, temp)
        
    return out

class Tree(object):
  def __init__(self, x, left=None, right=None):
    self.value = x
    self.left = left
    self.right = right 

x = Tree(1, Tree(0, Tree(1), Tree(3)), Tree(4))


def solution(t): 
    if not t: 
        return 0 
    
    stack = [(t, 0)]
    branchesSum = 0 
    
    while stack: 
        node, v = stack.pop() 
        if node.left or node.right:
        #depth first search 
        # the v is a little confusing to understand but easier to see in python tutor 
        # it goes from 1 to 10 to 100 etc. based on the height of the branch 
        # can probably do something like str() and converting back to int() as well 
            if node.left: 
                stack.append((node.left, node.value + v * 10)) 
            if node.right: 
                stack.append((node.right, node.value + v * 10)) 
        else: 
            branchesSum += node.value + v * 10 
    return branchesSum 

#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
import math 
def solution(t):
    if t is None: return [] 
    
    stack = [t] 
    result = []
    
    while len(stack) > 0: 
        result.append(max(tree.value for tree in stack)) 
        next_row = [tree.left for tree in stack if tree.left] + [tree.right for tree in stack if tree.right]
        stack = next_row 
    return result 


 #1. Add max value of ‘stack’ to result. 2. Create a new list of all next values for each value in stack. 3. redefine stack to this newly made list. 4. repeat 


#alternate solution 
def solution(t):
    largestValues = []
    q = []
    height = 0
    if t:
        q.append([t, height])
        while q:
            item = q.pop()
            node = item[0]
            currentHeight = item[1]
            if node.left:
                q.insert(0, [node.left, currentHeight + 1] )
            if node.right:
                q.insert(0, [node.right, currentHeight + 1])
            checkLargest(node.value, currentHeight, largestValues)
            
    return largestValues
    
        
def checkLargest(value, height, largestValues):
    if height == len(largestValues):
        largestValues.append(value)
    else:
        if largestValues[height] < value:
            largestValues[height] = value