🙏

জয়  শ্রী  রাম

🕉

---

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.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

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.

Instructor: