Summary - NP-completeness
- Algorithms course
- Expert
- Lesson 8/41
- 4 min
Print a problem classification in a mini task.
Summary - NP-completeness
In this group you learned P, NP and NP-complete concepts. Brute force solution, polynomial verification and reduction combine to clarify the classes.
Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.
Practice count_subsets function
Write count_subsets(arr, target). Return the number of subsets summing to target. Print 1 with print(count_subsets([3, 5, 7], 10)).
Starter code
def count_subsets(arr, target):
# Count subsets summing to targetSample solution
def count_subsets(arr, target):
# Count subsets summing to target
n = len(arr)
count = 0
for mask in range(1 << n):
s = 0
for i in range(n):
if mask & (1 << i):
s += arr[i]
if s == target:
count += 1
return count
print(count_subsets([3, 5, 7], 10))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 How long does it take to solve an NP-complete problem?
- Exponential time (worst case) Correct answer
- Polynomial time
- Constant time
- Logarithmic time
Explanation: Exponential time is needed in the worst case.
2 Bitmask loop
Question
for mask in range(1 ____ n):
Answer
for mask in range(1 << n):Explanation: << is right.
3 Summary - NP-completeness: match the terms
| Term | Meaning |
|---|---|
is_sorted |
P |
brute_force_subset |
NP-complete |
verify_subset |
Verification |
azaltma |
Reduction |