34. 순열

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.

itertools 모듈 사용

def permute(nums):
    return list(itertools.permutations(nums))

DFS를 활용한 순열 생성

def permute(nums):
    results = []
    prev_elements = []
    
    def dfs(elements):
    	#리프 노드를 만나게 되면 리프노드의 결과를 results에 저장하고 리턴한다.
        #리프노드일때 결과 추가
        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)
    return results

참조가 아닌 값을 복사하는 이유

• 파이썬은 모든 객체를 참조하는 형태로 처리된다.
• 즉, elements을 전달하게 되면 참조된 값이 변경될 경우 같이 바뀌게 된다.
• 따라서 순열 문제를 풀 때는 값만 복사되고 참조 같은 형태로 전달되지 않도록 주의해야 된다.

출처: 파이썬 알고리즘 인터뷰