[CHALLENGE] Break a number as a sum of given numbers

Question

Given a positive integer, express it as sum of input integers in any combination.
Eg-
given: 32
break it as: [4, 5]
4 + 4 + 4 + 4 + 4 + 4 + 4 + 4
OR
5 + 5 + 5 + 5 + 4 + 4 + 4

I don't know if this problem is even solvable 😂

Answer 1

It is possible by dynamic programming. And mine solution is in O(n^2) time. Do you want hear it?

Answer 2

Bartosz Pieszko i just solved it. though the code is not good right now (I was just trying to make the logic, so didn't end the infinite loop if num can't be broken), I'll share it with u. i am not quite sure what is dynamic programming but do share your code. always ready to learn more!
https://code.sololearn.com/cI3y8oZQAjEM/?ref=app

Answer 3

I'll try modifying it while you eat

Answer 4

@Bartosz Pieszko Yes, I also thought about applying dynamic programming here. So I'm starting to work on my code. However, I would really appreciate to see yours as well to compare.

Answer 5

well it's specifically for 4 and 5 & for 2 numbers to break into. so definitely not a one to be proud of 😂

Answer 6

Yours solution is only for your one input. It probably doesn't work for other inputs. My solution works for every numbers. I will write this after eating.

Answer 7

just discovered a lot of bugs in the logic. definitely not the solution.

Answer 8

by dynamic programming, are you guys pointing towards machine learning kind of solution?

Answer 9

@Aditya Rana You could probably add to the description that program should return "no combinations" if it is impossible like for 17 and (4,7).

Answer 10

I'm starting too. Count combinations are much easier than count this set of numbers to sum.

Answer 11

Nah, it's not machine learning. en.wikipedia.org/wiki/Dynamic_programming

Answer 12

Done.
https://code.sololearn.com/chXCtmQEVNp2/#py

:)

Answer 13

This code gives you all the solutions and lets you precise the numbers allowed in the sum. oneliner of course. https://code.sololearn.com/cWLGyFH7weto/?ref=app