Combination Sum
Application of 0/1 Knapsack Concept

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io
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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Instructor:
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
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn