#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 Solution:
    #number of permutations = n! 
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
    
        if len(nums) == 1: 
            return [nums[:]] 
        
        for i in range(len(nums)): 
            #pop off first element 
            n = nums.pop(0)
            
            #numswill now have one less value, will append popped value later 
            perms = self.permute(nums) 
            
            for perm in perms: 
                perm.append(n)
            
            result.extend(perms)
            #adding popped back 
            nums.append(n) 
        
        return result 
 

class Solution:

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        #i is index of candidates 
        def dfs(i, current, total): 
            if total == target: 
              #if you do not add .copu() it will append empty arrays 
                result.append(current.copy())
                return 
            if i >= len(candidates) or total > target: 
                return 

            #decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index 
            
            #1) try adding candidates[i]
            current.append(candidates[i])
            dfs(i, current, total + candidates[i])
            #2) move on to next index 
            current.pop() 
            dfs(i + 1, current, total)
        
        dfs(0, [], 0)
        return result 

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 
        
        

# //Tree Traversal (visit every node once) 
# //Heavy on recursion 
 
# //Breadth-first (BFS) vs. Depth-first (DFS) 
 
# // DFS: 
# // 1) in order (go in order of value)
# // 2) pre order (start at root)
# // 3) post order (start at botom)
 
 
# //When to use BFS vs. DFS: 
# //For a fully loaded (wide) tree, BFS queue will be overloaded in the start (overloaded space complexity)
# //For a longer tree, DFS will take more memory (more rare, Trees are usually wide)
# //Big O for both is same 
 
# //In order: useful if you want sorted array at end (you don't really know what the root is bc it's in the middle)
# //PreOrder: useful to "export a tree" so that it can be copied bc it flattens it 

class Node: 
  def __init__(self, value): 
    self.value = value 
    self.left = None 
    self.right = None 
 
class BinarySearchTree: 
  def __init__(self): 
    self.root = None 
 
  #adds number to correct place 
  def insert(self, value): 
    #creates new Node   
    new_node = Node(value) 
    #start at root 
    #if no root exists, root becomes new_node 
    if self.root == None: 
      self.root = new_node 
      return self 
    
    current = self.root 
    
    while True: 
      #to handle special case where value is same as current node 
      #you can return None or you can add a counter property 
      if value == current.value: 
        return None 
      #check to see if value is less than current 
      if value < current.value: 
        #check to see if there is node to left 
        #if not, add new_node to left 
        if current.left == None: 
          current.left = new_node 
          return self
        #if there is node to left, move to that node and repeat 
        current = current.left 
      #check to see if value is greater than current 
      else: 
        #check to see if there is node to right 
        #if not, add new_node to right 
        if current.right == None: 
          current.right = new_node 
          return self 
        #if there is node to right, move to that node and repeat 
        current = current.right 
        
  #Breadth first search iterative using queue 
  def BFS(self):
    node = self.root 
    #we will return data 
    data = [] 
    queue = [] 
    #place root node inside queue (recall FIFO)
    queue.append(node) 
    #while queue is not empty 
    while len(queue) > 0: 
      #dequeue node from queue and append to data  
      node = queue.pop(0)
      data.append(node) 
      #if there is left on node dequeued, add to queue 
      if node.left: 
        queue.append(node.left) 
      #if there is right on node dequeued, add to queue 
      if node.right: 
        queue.append(node.right) 
      #above two lines of code could be changed if it was a ternary tree, etc. instead of binary 
      #just loop for all children 
    return data 
  
  #parent down uses recursive 
  def DFSPreoder(self): 
    data = [] 
    #if you want to DFS not from root, create a variable here named current and specify which node to start from 
    #helper function 
    def traverse(node): 
      #all of root node's left will happen first, then right 
      #for other types of DFS, just tweak this order 
      data.append(node.value) 
      if node.left:
        traverse(node.left)
      if node.right: 
        traverse(node.right)
    
    traverse(self.root) 
    return data 
  
  #children up, root should be last value 
  def DFSPostOrder(self): 
    data = []
    
    def traverse(node): 
      if node.left:
        traverse(node.left)
      if node.right: 
        traverse(node.right)
      data.append(node.value)
    
    traverse(self.root)
    return data 
  
  #result data list should be sorted 
  def DFSInOrder(self):
    data = []
    def traverse(node): 
      if node.left: 
        traverse(node.left)
      data.push(node.value)
      if node.right: 
        traverse(node.right)
    traverse(self.root)
    return data 

t = BinarySearchTree() 
t.insert(1)
t.insert(5)
t.insert(6)
t.insert(2)
t.insert(0) 
t.insert(-1)
t.insert(7) 

print(t.DFSInOrder())

function getDef(element, def) {
  var str = ""

  var childs = element.childNodes
  for (var i = 0; i < childs.length; ++i) {
    if (childs[i].nodeType != 3) {
      str += childs[i].nodeName + " " + def + "<br />"
      str += getDef(childs[i], def + 1)
    }
  }

  return str
}


// Example
document.body.innerHTML = getDef(document.body, 0)

// ITERATIVE CODE : Time Complexity : Θ(n), Auxiliary Space : Θ(1)

import java.io.*;
import java.util.*;

public class Main {

	static int fact(int n)
	{
		int res = 1;

		for(int i=2; i<=n; i++)
		{
			res = res * i;
		}
		return res;
	}

	public static void main (String[] args) {
		
		int number = 5;

		System.out.println(fact(number));

	}
}

// RECURSIVE CODE : Time Complexity : Θ(n), Auxiliary Space : Θ(n) 

import java.io.*;
import java.util.*;

public class Main {

	
	static int fact(int n)
	{
	    if(n==0)
	        return 1;
		
		return n * fact(n-1);
	}

	public static void main (String[] args) {
		
		int number = 5;

		System.out.println(fact(number));

	}
}