P vs NP / NP-완전

from collections import Counter

def verify(nums, target, cert):                    # 인증서 검증: 다항 시간
    return not (Counter(cert) - Counter(nums)) and sum(cert) == target

def find(nums, target):                            # 답 찾기: 부분집합 2^n개를 확인
    n = len(nums)
    for mask in range(1 << n):
        sub = [nums[i] for i in range(n) if mask >> i & 1]
        if sum(sub) == target:
            return sub, mask + 1                  # (부분집합, 확인한 개수)
    return None, 1 << n

nums = [3, 34, 4, 12, 5, 2]
print(find(nums, 9))                           # ([4, 5], 21)
print(verify(nums, 9, [4, 5]), verify(nums, 9, [3, 34]))   # True False
print(find(nums, 13))                          # (None, 64)

from itertools import combinations

V = {0, 1, 2, 3, 4}
E = {(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)}

def is_clique(E, C):
    return all((a, b) in E or (b, a) in E for a, b in combinations(sorted(C), 2))

def complement(V, E):                          # 입력 변환: 보완 그래프를 만든다
    return {(a, b) for a, b in combinations(sorted(V), 2) if (a, b) not in E and (b, a) not in E}

def is_vertex_cover(E, S):
    return all(a in S or b in S for a, b in E)

Ec = complement(V, E)
C = {0, 1, 2}                                    # 크기 3인 클리크
print(is_clique(E, C), sorted(Ec), is_vertex_cover(Ec, V - C), len(V) - len(C))
# True [(0, 3), (0, 4), (1, 3), (1, 4), (2, 4)] True 2
print(is_clique(E, {2, 3, 4}), is_vertex_cover(Ec, V - {2, 3, 4}))   # False False

static boolean verify(int[] nums, int target, int[] cert) {
    List<Integer> pool = new ArrayList<>();
    for (int x : nums) pool.add(x);
    int sum = 0;
    for (int c : cert) {
        if (!pool.remove((Integer) c)) return false;   // 집합에 없는 원소(또는 중복 사용)
        sum += c;
    }
    return sum == target;
}

static int[] find(int[] nums, int target, int[] checked) {
    int n = nums.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) if ((mask >> i & 1) == 1) sum += nums[i];
        checked[0]++;
        if (sum == target) return pick(nums, mask);
    }
    return null;
}

static int[] pick(int[] nums, int mask) {          // 켜진 비트의 원소만 모은다
    return IntStream.range(0, nums.length).filter(i -> (mask >> i & 1) == 1).map(i -> nums[i]).toArray();
}

// nums = {3, 34, 4, 12, 5, 2}: find(target 9) → [4, 5] (확인 21번), verify(nums, 9, {4, 5}) → true
// find(target 13) → null (확인 64번)