Combination Sum
Application of Backtracking

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 an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Example 4:
Input: candidates = [1], target = 1
Output: [[1]]
Example 5:
Input: candidates = [1], target = 2
Output: [[1,1]]
Solution:
 NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rocksolid understanding.
I have put all the important pointers which are critical to design a correct algorithm and write bugfree code in the inline comments in the code below. This problem is an extension of the Combinations problems and so the solution for this problem would look strikingly similar to that of Combinations. So I highly recommend you to understand the algorithm for printing all Combinations really well before solving this problem. In the solution for computing Combinations we focus on the number of elements we need to have in a combination and make sure we have exactly k number of elements. For this problem, we should NOT be bothered about the number of elements we have in a combination. Rather, our focus should be that the sum of the elements in a combination is exactly same as the target, not one more not one less.
One of our missions at "The Algorists" is to show how knowing the basic concepts and solutions to the classic problems help you solve more complex problems seamlessly. As you progress in your software engineering career, you would realize that there is little glory in building every bits and pieces from scratch, but it the capability of extending and reusing prior work to build something greater and more impactful is what would make you a high caliber software engineer and architect, and would get you promoted quicker. What we are doing here (leveraging our knowledge and learnings from solving a different but related problem, which is computing Combinations in this case) is a small scale exercise for extending other software solution.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Don't forget to take indepth look at the other backtracking problems because that is what would make you comfortable with using the backtracking template and master the art of Backtracking:
 Letter Case Permutation
 Power Set
 All Paths Between Two Nodes
 Word Search
 Sudoku
 NQueens
 Word Square
 Generate Parentheses
The above content is written by:
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