On.

순열과 조합

순열

• 원소를 뽑아서 순서대로 나열하기 까지 해야 함.
• 똑같은 원소가 모여도, 순서가 같지 않으면 다른 것으로 본다.

## ex.
[1,2,3] 이랑 [1,3,2]는 원소는 같지만 순서가 다르므로, 다른 것이라고 판단!

## 순열 구현
def permute(nums):
    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)
    return results

조합

• 원소를 뽑기만 함. 순열처럼 순서를 생각하지 않음

## ex.
[1,2,3] 이랑 [1,3,2]은 걍 같은 조합이라, 걍 [1,2,3]임

## 조합 구현
def combine(n, k):
    results = []

    def dfs(elements, start, k):
        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)
    return results

Off.

프로그래머스 100위 진입 가즈아!!! 🔥🔥🔥