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:


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:



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



Help Your Friends save 40% on our products

wave