dfs

전화번호 조합

def LetterCombinations(self, digits: str) -> List[str] :
	def dfs(index, path) : 
    	if len(path) == len(digits) :
        	result.append(path)
            return
     	
        for i in ranage(index, len(digits) :
        	for j in dic[digits[i]] : 
            	dfs(i+1, path+j) 
    if not digits : 
    	return []
   dic = {}
   dfs(0, "")
   return result

순열

def permute(self, nums: List[int]) -> List[List[int]] :
	results = []
    prev_elements = []
    
    def dfs(elements) : 
    	if len(elements) == 0 :
        	results.append(prev_elements[:])
       
        for e in elements :
        	next_elements = elements[:]
            next_elements.remove(e)
            
            prev_elements.append(e)
            dfs(next_elements)
            prev_elements.pop()
    dfs(nums)    

def permute ( self,  nums: List[int]) -> List[List[int]] ):
	return list(intertools.permutations(nums)) 

조합

def combine (self, n: int, k: int) -> List[List[int]] :
	results = []
    
    def dfs (elements, start: int, k: int): 
    	if k == 0 :
        	results.append(elements[:]) 
        for i in range(start, n+1) :
        	elements.append(i) 
            dfs(elements, i+1, k-1) 
            elements.pop()
    dfs ( [], 1, k) 

def combine (self, n: int, k: int) -> List[List[int]] : 
	return list(itertools.combinations(range(1, n+1), k)

조합의 합

def combinationSum (self, candidates: List[int]. target: int) -> List[List[int]] :
	result = []
    
    def dfs(csum, index, path) :
		if csum < = 0 :
        	return
        if csum == 0 :
        	result.append(path)
            return
        for i in range(index, len(candidates))
        	dfs(csum-candidates[i] , i, path+candidates[i])
    dfs(target, 0, [])
    return result

부분집합

def subsets(self, nums: List[int] -> List[List[int]]):
	result = []
    
    def dfs(index, path) :
    	result.append(path)
        
        for i in range(index, len(nums) :
        	dfs(i+1, path+[nums[i]])
            
    dfs(0, [])