Try to face the integration by parts

Good evening. It's been a long time (* ´ω `)

This challenge is from an array containing arbitrary elements Randomly select elements and add them together. But it's not just about adding up It must be added up to reach the target value.

For example, choose a combination from the array so that the total is 20 !! It's something like that.

Somewhat (; ´ ・ ω ・)

It seems to be quite famous and basic content, I personally had a hard time (laughs)

Suddenly, I will put the code.

Partial_sum.py


def solve(Nlist, target,  i=0, sum=0):
    if i == len(Nlist):
        return sum == target
    if (solve(Nlist, target, i + 1, sum)):
        return True
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
    return False

Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))

It's simpler than you think, but it's complicated. For example, At first I will only look here.

Partial_sum.py


#Start from here!! 
Nlist = [1,3,5,12,7]
target = 11
#          ↓[1,3,4...] ↓ 11
print(solve(Nlist, target))

Throw Nlist and target into solve. As an image, an array containing elements and the target total value Just throw the whole thing and say hello !! Let's take a look inside solve.

Partial_sum.py


#i is an image of your current location.
#sum is the sum of the current numbers.
#You are at 0,The total value is also 0
def solve(Nlist, target,  i=0, sum=0):
    #Nlist is 5 in length, initially i==Since it is 0, Pass!!
    if i == len(Nlist):
        return sum == target
    #that?!There is more solve in the if statement. I don't know!!
    #Let's stop reading(Lol)
    if (solve(Nlist, target, i + 1, sum)):

I don't know, I want to throw it out (laughs).

No! Run away. .. The answer is that if you have recursion in your if statement, Complete the recursive process and derive true or false. This determines whether or not it is included in the if statement. Hmm, stupid (laughs)

Do you want to leave for the time being? of solve (Nlist, target, i + 1, sum) in if For an adventure to find out what's ahead.

Let's go in order (`) ノ

i=0.py


def solve(Nlist, target,  i=0, sum=0):
    #pass!
    if i == len(Nlist):
        return sum == target
    #Recursive processing is continued until it is clear whether the conditional statement of the if statement is True or False.
    if (solve(Nlist, target, i + 1, sum)):
        return True

i=1.py


#solve(Nlist,target,1(=0+1),0)I entered the recursive process with.
def solve(Nlist, target,  i=1, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #It is also recursive processing. Let's go without fear!!
    if (solve(Nlist, target, i + 1, sum)):
        return True

i=2.py


#solve(Nlist,target,2(=1+1),0)I entered the recursive process with.
def solve(Nlist, target,  i=2, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #It is also recursive processing. Let's go without fear!!
    if (solve(Nlist, target, i + 1, sum)):
        return True

i=3.py


#solve(Nlist,target,3(=2+1),0)I entered the recursive process with.
def solve(Nlist, target,  i=3, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #It is also recursive processing. Let's go without fear!!
    if (solve(Nlist, target, i + 1, sum)):
        return True

i=4.py


#solve(Nlist,target,4(=3+1),0)I entered the recursive process with.
def solve(Nlist, target,  i=4, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #It is also recursive processing. Let's go without fear!!
    if (solve(Nlist, target, i + 1, sum)):
        return True

i=5.py


#solve(Nlist,target,5(=4+1),0)I entered the recursive process with.
def solve(Nlist, target,  i=5, sum=0):
    #i == len(Nlist) ==Finally, in 5, I put it in the if statement at the beginning.
    if i == len(Nlist):
        #But unfortunately sum(0) != target(11)。False
        return sum == target

I see, I went to i = 5, but it turned out to be False. What happens after that? .. For the time being, the result of i = 5 was False, so Let's take it back to the previous layer, i = 4.

i=4.py


def solve(Nlist, target,  i=4, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #The conditional statement in the if minute was Flase. That is, the if statement here is pass!!
    #Let's go to the next if statement!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #Here i=4 so let's substitute
    #  (solve(Nlist, target, 4 + 1, sum + Nlist[4]))
    #  (solve(Nlist, target,   5  , 0   + 7        ) //Nlist = [1,3,5,12,7]
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True

Yes, move on to the next if statement. Let's check again when i = 5 with a new conditional statement.

i=5.py


#solve(Nlist,target,5,7)I entered the recursive process with.
def solve(Nlist, target,  i=5, sum=7):
    #i == len(Nlist) == 5 ,Put it in the if statement.
    if i == len(Nlist):
        #But unfortunately sum(7) != target(11)。False
        return sum == target

I think that the figure up to this point will look like the one below. 図2.PNG A good person can do this with his head, I couldn't do it myself, so I wrote it on paper and organized it. Returning to the story, it seems that nothing was done until i = 4. Now let's report this result to i = 3.

i=3.py


#solve(Nlist,target,3(=2+1),0)I entered the recursive process with.
def solve(Nlist, target,  i=3, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #False so pass!! 
    #Sum has never been 11 from previous processing
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #  (solve(Nlist, target, 3 + 1, sum + Nlist[3])): //Nlist = [1,3,5,12,7]
    #  (solve(Nlist, target,   4  ,  0  +    12   )):
    #Substitute the above conditions below and enter a new if!!                 
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True

i=4.py


#solve(Nlist,target,4(=3+1),12)I entered the recursive process with.
def solve(Nlist, target,  i=4, sum=12):
    #pass!!
    if i == len(Nlist):
        return sum == target

    #It is a recursive process. Let's go without fear!!
    if (solve(Nlist, target, i + 1, sum)):
        return True

i=5.py


#solve(Nlist,target,5(=4+1),12)I entered the recursive process with.
def solve(Nlist, target,  i=5, sum=12):
    #i == len(Nlist) == 5 ,Put it in the if statement.
    if i == len(Nlist):
        #But unfortunately sum(12) != target(11)。False
        return sum == target

It was false, I will go back one report.

i=4.py


#solve(Nlist,target,4(=3+1),12)I entered the recursive process with.
def solve(Nlist, target,  i=4, sum=12):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #False with Pass!
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #Next↓
    if (solve(Nlist, target, i + 1, sum + Nlist[i]))://Nlist = [1,3,5,12,7]
        return True

i=5.py


#solve(Nlist,target,5(=4+1),12 + 7)I entered the recursive process with.
def solve(Nlist, target,  i=5, sum=19):
    #i == len(Nlist) == 5 ,Put it in the if statement.
    if i == len(Nlist):
        #But unfortunately sum(19) != target(11)。False
        return sum == target

Let's make a figure. 図3.PNG I want to see the tree structure (laughs) It's a long task, but it's oK if you keep the following points in mind.

** 1. The conditional statement (recursive) of the if statement keeps chasing until True and False are seen. 2. If you see True or False, go back to the previous layer and follow the description in solve faithfully to follow the action **

I wrote it brilliantly, but I didn't know it at all, so To see what is transitioning I mixed pirnt as follows.

Partial_sum.py


def solve(Nlist, target,  i=0, sum=0):
    print(f"i:{i},sum:{sum}") #Display the current value for clarity during recursive processing
    if i == len(Nlist):
        #For recursive processing, put the conditional statement when you come to the bottom layer at the beginning.
        #So, print a comment that tells you that the bottom layer is when you enter this if statement.
        print(f"Result:i={i},sum={sum}") 
        print() #Line breaks to separate from the next process
        return sum == target
    if (solve(Nlist, target, i + 1, sum)):
        return True
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
    return False

Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))

Let's see the execution result !!

Execution result.py


i:0,sum:0
i:1,sum:0
i:2,sum:0
i:3,sum:0
i:4,sum:0
i:5,sum:0
Result:i=5,sum=0
#↑ Compare with the above figure. i,Does the change in sum match the figure?
#Result:i=5,sum=Returns False because sum is not 11 as it says 0
#I after returning=I'll be back at 4.
#After returning, continue to the next IF statement.
#Therefore, the next display is i below=It becomes pirnt at the time of 5.
#If you don't understand, please return to the above page.
i:5,sum:7
Result:i=5,sum=7
#↑sum(=7) !=Since it is 11, it is False.
#Therefore, i=The two if statements at 4 are both False.
#Next is i=It returns to the if statement at the time of 3, but the processing is the same as above.
i:4,sum:12
i:5,sum:12
Result:i=5,sum=12

i:5,sum:19
Result:i=5,sum=19

i:3,sum:5
i:4,sum:5
i:5,sum:5
Result:i=5,sum=5

i:5,sum:12
Result:i=5,sum=12

i:4,sum:17
i:5,sum:17
Result:i=5,sum=17

i:5,sum:24
Result:i=5,sum=24

i:2,sum:3
i:3,sum:3
i:4,sum:3
i:5,sum:3
Result:i=5,sum=3

i:5,sum:10
Result:i=5,sum=10

i:4,sum:15
i:5,sum:15
Result:i=5,sum=15

i:5,sum:22
Result:i=5,sum=22

i:3,sum:8
i:4,sum:8
i:5,sum:8
Result:i=5,sum=8

i:5,sum:15
Result:i=5,sum=15

i:4,sum:20
i:5,sum:20
Result:i=5,sum=20

i:5,sum:27
Result:i=5,sum=27

i:1,sum:1
i:2,sum:1
i:3,sum:1
i:4,sum:1
i:5,sum:1
Result:i=5,sum=1

i:5,sum:8
Result:i=5,sum=8

i:4,sum:13
i:5,sum:13
Result:i=5,sum=13

i:5,sum:20
Result:i=5,sum=20

i:3,sum:6
i:4,sum:6
i:5,sum:6
Result:i=5,sum=6

i:5,sum:13
Result:i=5,sum=13

i:4,sum:18
i:5,sum:18
Result:i=5,sum=18

i:5,sum:25
Result:i=5,sum=25

i:2,sum:4
i:3,sum:4
i:4,sum:4
i:5,sum:4
Result:i=5,sum=4

i:5,sum:11
Result:i=5,sum=11

True

As mentioned above, after reaching the limit where transition is not possible The method of repeating the process of returning one step and operating to the limit is called ** depth-first search **. The material says that it is relatively easy to write, No, it's awesome for beginners !! (゚ Д ゚)

It seems that the future is still long (* ´ω `)

Recommended Posts

Try to face the integration by parts
Try to introduce the theme to Pelican
Cython to try in the shortest
The fastest way to try EfficientNet
The easiest way to try PyQtGraph
Try to implement and understand the segment tree step by step (python)
Try to predict the triplet of boat race by ranking learning
Try the Microsoft Cognitive Services Face API
Python amateurs try to summarize the list ①
Try to classify O'Reilly books by clustering
Try to solve the fizzbuzz problem with Keras
Try adding fisheye lens distortion to the image
Try to forecast power demand by machine learning
Try to decompose the daimyo procession into Tucker
Try to solve the Python class inheritance problem
Try to solve the man-machine chart with Python
How to try the friends-of-friends algorithm with pyfof
How to erase the characters output by Python
Download the VGG Face2 dataset directly to the server
Try to simulate the movement of the solar system
Try posting to Qiita for the first time
Try to make a blackjack strategy by reinforcement learning (② Register the environment in gym)
Upload the image downloaded by requests directly to S3
[Python] Try to read the cool answer to the FizzBuzz problem
Try setting NETCONF (ncclient) from software to the router
Try to solve the problems / problems of "Matrix Programmer" (Chapter 1)
Try to visualize the room with Raspberry Pi, part 1
Try to solve the internship assignment problem with Python
Molecular dynamics simulation to try for the time being
Save the graph drawn by pyqtgraph to an image
Try to estimate the number of likes on Twitter
Read the xml file by referring to the Python tutorial
Try to get the contents of Word with Golang
[Neo4J] ④ Try to handle the graph structure with Cypher
How to check the Java version used by Maven
Try to decipher the login data stored in Firefox
Try to specify the axis with PyTorch's Softmax function
How to unprefix the DB name used by pytest-django
Try refactoring step by step
Try to implement yolact
The road to Pythonista
The road to Djangoist
Try to import to the database by manipulating ShapeFile of national land numerical information with Python
Try to get the function list of Python> os package
Try to evaluate the performance of machine learning / regression model
Try to play with the uprobe that supports Systemtap directly
I want to save the photos sent by LINE to S3
Try connecting to Supervisord via XMLRPC to start / stop the program
How to switch the configuration file to be read by Python
How to test the attributes added by add_request_method of pyramid
[Selenium/Python] Try to display the court case pdf at once
Try to evaluate the performance of machine learning / classification model
[Django] Pass the user instance authenticated by API to ModelSerializer
Try to improve the accuracy of Twitter like number estimation
[Python] Try to classify ramen shops by natural language processing
Try to solve the problems / problems of "Matrix Programmer" (Chapter 0 Functions)
Try to automate the operation of network devices with Python
Create AI to identify Zuckerberg's face by deep learning ③ (Data learning)
Debug by attaching to the Python process of the SSH destination
Try to extract the keywords that are popular in COTOHA
Try to model a multimodal distribution using the EM algorithm