Subsets

+10

서로 다른 정수로 이루어진 목록 nums가 주어집니다. 빈 부분집합과 전체 목록을 포함하여 모든 부분집합을 반환하세요. 따라서 n개의 값은 2^n개의 부분집합을 만듭니다. 각 부분집합의 값은 오름차순으로 정렬하고, 부분집합은 사전식 순서로 나열하세요. 두 부분집합을 값별로 비교하여 처음 다른 값으로 순서를 정하고, 한 부분집합이 다른 부분집합의 시작 부분이면 먼저 옵니다. [1, 2]의 경우 답은 [[], [1], [1, 2], [2]]입니다.

함수

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: 순서는 상관없으며, 모두 서로 다른 값
반환값integer-2d-array: 각 부분집합은 오름차순으로 정렬되고, 사전순으로 나열됩니다

제약 조건

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
nums의 모든 값은 서로 다릅니다.
nums는 어떤 순서로든 주어질 수 있습니다.

예제

입력: nums = [3, 1, 2]
출력: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
설명: 정렬하면 값은 1, 2, 3이고, 값이 세 개이므로 부분집합은 2^3 = 8개입니다. [1, 2]는 [1, 2, 3]의 시작 부분이므로 그 앞에 오고, 두 번째 위치에서 2가 3보다 작으므로 [1, 2, 3]은 [1, 3]보다 앞에 옵니다.

입력: nums = [0]
출력: [[], [0]]
설명: 하나의 값에는 두 개의 부분집합이 있습니다. 값을 제외하면 []가 되고, 포함하면 [0]이 됩니다. 빈 부분집합이 항상 먼저 옵니다.

입력: nums = [5, -2]
출력: [[], [-2], [-2, 5], [5]]
설명: 값은 -2와 5 순으로 정렬되므로 [-2, 5]는 그 순서대로 작성됩니다. -2를 포함하는 모든 부분집합은 -2가 5보다 작으므로 [5]보다 앞에 옵니다.

후속 질문

재귀를 사용하지 않고, 바로 이전 부분 집합에서 각 부분 집합을 직접 만들어 같은 목록을 생성할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

부분집합은 2^n개이므로 어떤 방법도 O(2^n)보다 적은 작업을 수행할 수 없습니다. 핵심은 나중에 1024개의 목록을 정렬하지 않고, 각 부분집합을 필요한 순서대로 한 번씩 생성하는 방법입니다. 정렬된 값들을 대상으로 백트래킹하면서 결정 트리의 각 노드에 진입할 때마다 기록하면 부분집합을 정확히 사전순으로 순회합니다.

비트마스크를 사용한 다음 정렬

핵심 아이디어

정렬된 값들을 위치 0부터 n-1까지 차례로 놓습니다. 부분집합은 각 위치에 대해 포함 여부를 나타내며, 숫자의 n개 비트가 바로 그 역할을 합니다. 따라서 0부터 2^n-1까지의 숫자가 부분집합에 해당합니다. [1, 2, 3]의 경우 마스크 5는 2진수 101이므로 비트 0과 2가 켜져 있고, [1, 3]을 나타냅니다. 마스크 0은 공집합이고 마스크 7은 전체 목록입니다.

서로 다른 마스크는 서로 다른 부분집합을 나타내며 모든 부분집합에는 마스크가 있으므로, 반복문은 2^n개의 모든 부분집합을 정확히 한 번씩 생성합니다. 정렬된 값들을 기준으로 위치 0부터 비트를 읽으면 각 부분집합의 값들이 오름차순으로 만들어집니다.

마스크는 문제에서 요구하는 순서대로 나오지 않습니다. 마스크 1은 [1], 마스크 2는 [2], 마스크 3은 [1, 2]이므로 [2]가 [1, 2]보다 앞에 오게 됩니다. 값을 하나씩 비교하고 접두 부분집합을 먼저 두는 비교 함수를 사용하는 정렬로 이 문제를 해결할 수 있습니다. 정렬에는 생성보다 더 많은 비용이 듭니다. 2^n개의 부분집합에는 약 n × 2^n번의 비교가 필요하고, 비교할 때마다 최대 n개의 값을 읽습니다. n = 10일 때 약 10^5번 읽는 정도로 여전히 빠르지만, 다음 접근법에서는 전혀 하지 않는 작업입니다.

알고리즘

nums를 정렬하여 모든 부분 집합이 오름차순으로 읽히도록 합니다.
0부터 2^n-1까지 모든 마스크에 대해, 비트가 설정된 위치의 값을 모읍니다.
부분 집합 목록을 정렬합니다. 두 부분 집합이 처음으로 달라지는 위치에서 더 작은 값이 우선하며, 한쪽이 먼저 끝나면 그쪽이 먼저 옵니다.
정렬된 목록을 반환합니다.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

백트래킹: 선택하고, 탐색하고, 선택을 취소하기

핵심 아이디어

부분 집합을 트리로 생각해 보세요. 루트는 빈 부분 집합입니다. 노드 아래에는 마지막으로 추가한 값보다 큰 값이라면 무엇이든 추가할 수 있습니다. 정렬된 값 [1, 2, 3]의 경우 루트에는 자식 [1], [2], [3]이 있고, [1]에는 자식 [1, 2]와 [1, 3]이 있으며, [1, 2]에는 자식 [1, 2, 3]이 있습니다. 각 부분 집합은 오름차순으로 쓰는 방법이 하나뿐이므로 이 트리에 정확히 한 번 나타나며, 리프뿐 아니라 모든 노드가 답입니다.

백트래킹은 하나의 공유 리스트 path를 사용해 트리를 탐색합니다. 자식으로 내려가려면 선택합니다. 값을 추가합니다. 탐색합니다. 재귀 호출을 하고, 도우미 함수는 도착하는 순간 path의 복사본을 기록합니다. 그런 다음 선택 취소를 합니다. 값을 제거하여 path가 부모 노드의 상태로 돌아가게 하고, 다음 형제 노드를 시도할 수 있게 합니다. 들어가는 길에 모든 노드를 기록하므로 부모는 항상 자식보다 먼저 기록됩니다.

그래서 정렬하지 않아도 출력이 사전순으로 나옵니다. 각 노드의 자식은 가장 작은 값부터 시도하고, 다음 분기를 시작하기 전에 현재 분기 전체의 탐색을 마칩니다. [1, 2, 3]의 경우 [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]을 기록합니다. 이는 사전의 순서와 같으며, 접두사가 그 확장된 항목보다 먼저 옵니다.

트리에는 노드가 2^n개 있고 경로를 복사하는 데 최대 n의 비용이 들므로, 시간 복잡도는 답 자체의 크기인 O(n × 2^n)입니다. 출력 외에는 경로 하나와 호출 스택을 유지하며, 둘 다 깊이는 최대 n입니다.

알고리즘

값을 정렬합니다.
explore(start)를 작성합니다. 먼저 path의 복사본을 결과에 추가합니다.
그런 다음 start부터 끝까지 각 인덱스 i에 대해 values[i]를 path에 추가하고(선택), explore(i+1)을 호출한 다음(탐색), 마지막 값을 제거합니다(선택 취소).
빈 경로로 explore(0)을 호출하고 결과를 반환합니다.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

함정과 경계 사례

여기서 오답이 나오는 가장 흔한 원인은 순서나 하나의 리스트를 공유하는 문제입니다.

복사본 대신 path 자체를 추가하는 경우입니다. 그러면 모든 항목이 같은 리스트를 가리키며, 탐색이 끝났을 때 그 리스트는 비어 있으므로 []의 사본을 2^n개 반환하게 됩니다.
nums를 정렬하지 않는 경우입니다. [3, 1, 2]에서는 트리가 [3, 1]을 만들며, 이는 오름차순이 아니므로 탐색 순서가 더 이상 사전식 순서가 아닙니다.
순열에서 하듯 리프에서만 기록하는 경우입니다. 이 트리의 모든 노드는 부분집합이므로, 끝까지 도달한 경로만 기록하면 부분집합을 너무 적게 반환합니다.
i+1 대신 start+1로 재귀 호출하는 경우입니다. 그러면 값이 더 큰 값 뒤에 오거나 심지어 자기 자신 뒤에 올 수 있어, 오름차순 부분집합이 아닌 [3, 2]나 [3, 3] 같은 리스트가 만들어집니다.
포함 또는 제외 트리(값 0을 결정한 다음 값 1을 결정하는 방식 등)를 사용하고 리프에서 기록하는 경우입니다. 이렇게 하면 2^n개의 모든 부분집합을 찾지만, 포함을 먼저 시도하면 전체 리스트가 맨 앞에 오고, 제외를 먼저 시도하면 [3]이 [2]보다 앞에 옵니다. 둘 다 사전식 순서가 아닙니다.
길이를 먼저 기준으로 정렬하는 비교기를 사용하면 [], [1], [2], [3], [1, 2] 순서가 되는데, 이는 다른 순서입니다.

자주 묻는 질문3

n개의 원소를 가진 집합은 부분집합을 몇 개 갖나요?

2^n. 각 원소는 다른 원소와 독립적으로 포함되거나 포함되지 않으므로, 선택지가 곱해집니다. 첫 번째 원소에 대해 두 가지, 두 번째 원소에 대해 두 가지, 이런 식입니다. 값이 세 개이면 공집합과 전체 집합을 포함해 부분집합이 8개이고, 열 개이면 1024개입니다.

Subsets 문제의 시간 복잡도는 얼마인가요?

O(n × 2^n). 부분집합은 2^n개이고 하나를 출력하는 데 최대 n단계가 걸리므로, 답을 반환하는 것만으로도 그만큼의 비용이 듭니다. 백트래킹은 이 경계에 도달하며 추가 공간은 O(n)만 사용합니다. 비트마스크를 사용해 생성하는 방법도 같은 속도지만, 결과를 나중에 정렬하면 n만큼의 요소가 추가됩니다.

부분 집합을 구할 때 백트래킹을 사용해야 할까요, 아니면 비트마스크를 사용해야 할까요?

비트마스크는 코드가 짧고 재귀가 필요 없으며, 포함 또는 제외 선택을 비트로 명확하게 보여 줍니다. 백트래킹은 그 자체로 부분집합을 사전순으로 생성하며, 중복 값 건너뛰기, 크기가 k인 부분집합만 선택하기, 목표 합에 도달하는 부분집합만 선택하기 등 일반적인 변형에도 적용할 수 있습니다. 이때는 분기를 일찍 탐색 중단할 수 있습니다.

def subsets(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [3, 1, 2]

예상 출력

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]