• Customer Support: admin@thealgorists.com
  • Feedback: 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: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


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.

Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Solution:


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 Set in our code, since Set does not contain any duplicate unlike in List.

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.




PRO TIP:


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:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave