🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.

Example 4:
Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

Example 5:
Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
​​​​​​​There are no other valid combinations.

Constraints:
2 <= k <= 9
1 <= n <= 60

Solution:

Please go through the following problems before going through this one:

• 0/1 Knapsack Problem
• Subset Sum Problem
  Partition Equal Subset Sum
• Count Subset Sum
• Minimum Subset Sum Difference
• Target Sum
• Combination Sum

The fact that "Each number is used at most once" is an indicator that this problem could be solved using 0/1 Knapsack Concept. In fact, this problem could be seen as follows:

• Fill up a knapsack with target amount of weight where we have 9 items with weight 1 to 9 and we are allowed to use any item only once.
  But this problem we have one more very important constraint: we can use only k number of items.

Since we have already figured out that this problem is a variation of 0/1 Knapsack Problem we already know how we are going to design the algorithm.

For every number (1 to 9) we have option to either include it or exclude it, keeping in mind the contraint of mandatory k number of items we need to include, as we see in the code below:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Instructor: