Customer Support: firstname.lastname@example.org
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
- If you are a student, email to email@example.com to get special student discount.
Given a collection of non-zero positive numbers numbers and a target number, find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
The solution set must not contain duplicate combinations.
Input: candidates = [10,1,2,7,6,1,5], target = 8
Input: candidates = [2,5,2,1,2], target = 5
The fact that " Each number in candidates may only be used once in the combination" is an indicator that this problem could be solved using 0/1 Knapsack Concept. In fact, this problem could be thought of as following:
- Put exactly target amount of weight in knapsack making sure that that no item is used more than one.
The above thought process bring us to the infer that this is a variation of Classic 0/1 Knapsack Problem. For each item we have an option to either include or exclude it. Since we need to print all the combinations we would be considering both cases (include and exclude) and include combinations we get for both cases. We do not need any duplicate combinations, as discussed in the problem statement. That is why we would be using
Setin our code, since
Setdoes not contain any duplicate unlike in
It is very important to get familiar with the space optimized code template discussed in Classic 0/1 Knapsack Problem, before looking at the code below.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
In a coding interview never forget to do a dry run of your code and do a thorough testing. Never wait for the interviewer to ask you to test the code you have written. Try to find out any bug your code might have before the interviewer points it out. For more interview tips visit interview Tips.
The above content is written by:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn