Beta
Subset Sum Problem
16At1029
Loading description...
Dynamic Programming
Algorithms
View
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Python new test frameworks to be used.
This famous problem is NPC. Please provide constraints.
This comment has been hidden.
I don't think a greedy solution would work here... Consider arr = [3,6,7,9] and K = 10, a subset would be {7,3}. Let's look at all the conditions in your for loop: len(res) != 0, so the first condition fails total != 0, so the second condition fails total - res[-1] (10 - 9) > 0, so the third condition (if) fails total - res[-1] (10 - 9) != 0, so the third condition (elif) fails
Now from your else, total = 10 - 9 = 1 Since there is no 1 in the original array, your code will loop through the array and incorrectly output False.
Thank you for your insight. Do you mind disclosing what kind of solution would work here?
This comment has been hidden.
Just a quick question, the subset can be greater than two values correct? For example, the k value can be 9 and the subset is {1,3,5}.
That's right
Random generator should be put in the test fixture, not in Preloaded.
Fixed!
ah sorry, marked as resolved
The tests almost always expect the same result.
Mostly fixed!