Solve the subset sum problem with a full search in Python

Problem (Arimoto P.34)

The integers a1, a2, ...., an are given. Choose some of them and determine if the sum can be just k.

#input
n = int(input())
a = list(map(int, input().split()))
k = int(input())

#Variables for judgment
cnt = 0

#Full search
for i in range(1<<len(a)):
    l = []
    for j in range(len(a)):
        if (i>>j & 1) == 1:
            l.append(a[j])
    if sum(l) == k:
        cnt += 1
print('Yes' if cnt>=1 else 'No')

Recommended Posts

Solve the subset sum problem with a full search in Python
Search the maze with the python A * algorithm
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve the maximum subarray problem in Python
I wanted to solve the ABC164 A ~ D problem with Python
Solve the Python knapsack problem with a branch and bound method
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
[Python] Get the files in a folder with Python
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
Try to solve the internship assignment problem with Python
Full bit search with Python
Solve the Python asymmetric traveling salesman problem with a branch and bound method
I tried to solve the problem with Python Vol.1
Implement a circular expression binary search in Python. There is a comparison with a simple full search.
Solve the Japanese problem when using the CSV module in Python.
Write a binary search in Python
Solve ABC163 A ~ C with Python
Solve ABC166 A ~ D with Python
ABC166 in Python A ~ C problem
Solve ABC168 A ~ C with Python
Solve ABC036 A ~ C in Python
Write a depth-first search in Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC037 A ~ C in Python
I want to do a full text search with elasticsearch + python
Read a file in Python with a relative path from the program
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Solve ABC175 A, B, C in Python
Write the test in a python docstring
Run the Python interpreter in a script
Solve AtCoder ABC168 with python (A ~ D)
Solve ABC165 A, B, D in Python
Solve the traveling salesman problem with OR-Tools
In search of the fastest FizzBuzz in Python
I tried "Implementing a genetic algorithm (GA) in python to solve the traveling salesman problem (TSP)"
A memo organized by renaming the file names in the folder with python
The 16th offline real-time how to write reference problem to solve with Python
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
Receive a list of the results of parallel processing in Python with starmap
Create a record with attachments in KINTONE using the Python requests module
The 19th offline real-time how to write reference problem to solve with Python
Try to solve a set problem of high school math with Python
About bit full search that often appears in competition pros From the eyes of beginners with python
Try to solve the fizzbuzz problem with Keras
Load the network modeled with Rhinoceros in Python ③
Try to calculate a statistical problem in Python
Try to solve the Python class inheritance problem
Get the caller of a function in Python
The first step in the constraint satisfaction problem in Python
Try to solve the man-machine chart with Python
[Automation] Extract the table in PDF with Python
Create a virtual environment with conda in Python
Make a copy of the list in Python
Solve A ~ D of yuki coder 247 with python
The 18th offline real-time writing problem in Python
Load the network modeled with Rhinoceros in Python ②
[At Coder] Solve the problem of binary search
Create a new page in confluence with Python
Output in the form of a python array
[Python] Find the transposed matrix in a comprehension